北京工业大学2001年数据结构试题及答案
一．多选填空题。1．一个栈的入站元素序列是1，2，3，4，5若允许出栈操作可在任意可能的时刻进行，则下面的序列中。不可能出现的出栈序列是（），理由是（）。A．3，4，2，5，1B．2，5，4，1，3C．2，3，1，5，4D．3，5，4，2，12．一棵二叉树的前序遍历序列为ABCDEFG，它的中序序列可能是（）A．CABDEFGB．ABCDEFGC．DACEFBGD．BADCFEG3．下面结构中最适于表示稀疏无向图的是（），适于表示有向图的是（）A．邻接矩阵B．逆邻接表C．邻接多重表D．十字链表E．邻接表4．采用败者树进行K路平衡归并时，总的（包括访外）效率与K（）A．有关B．无关5．N个顶点连通无向图的邻接矩阵至少有（）个非0元素，至多有（）个非0元素；
个顶点的强连通有向图至少有（）条弧。6．含4个度为2的结点和5个叶子结点的二叉树，可有（）个度为1的结点。二．简答题1．上三角阵A（NN）按行主序压缩存放在数组B中，其中AIjBK写出用I，J表示的K。2．画出广义表A（a（b）c）的第一种存储结构（表结点第二指针指向余表）图，并用取首元（head）和取尾元（tail）函数表示原子c。3．证明：在二叉树的三种遍历序列中，所有叶子结点间的先后关系都是相同的。要求每步论断都指出根据。4．是述哈希表中不成功的平均查找长度概念，求法，和理由。5．对于输入关键字序列48，70，65，33，24，56，12，92进行：a建立堆排序的初始堆（小顶堆），要求画出主要过程。b建一棵平衡二叉树，画出过程（至少每次调整有一张，标出最小不平衡子树的根）。三．下面程序段实现用尾指针表示，带头结点单链环的操作，请补足空缺部分。typederstruct
odeprogrampppElemtypekeytypeelemtypecharStruct
ode
extli
k
odeNodeli
k
oderecord
fKeyelemtype
extli
kOidi
itlli
kpe
d
C语言
Voidi
sli
kpi
tIelemtypeei
tjli
kqsqp
extj0whileqpjI1qq
extjif②填空exiterrorsli
kmallocsizeof
odeskeyes
extq
extsq
exts维护③填空retur
voiddelli
kpi
tIelemtypeei
tjli
kqsqp
extj0whileqpjI1qa
extjif④填空exiterrorsq
extq
exts
exteskey维护⑤填空freesretur
fi
dli
kpelemtypeei
tIli
kqqp
ext⑥填空qq
extI1while⑦填空qq
extIifqp
extretur
0elseretur
I循环条件中只有一次比较
类PASCAL语言
proci
itvarpli
kbegi
①填空e
dproci
svarpli
kIi
tegereelemtypevarji
tegerqsli
kbegr