发布时间 : 星期一 文章太原理工大学数据结构试题入学考试库集及答案更新完毕开始阅读
用C语言实现该程序，该程序应具有一定的错误处理能力。(提示：使用命令行参数) 注意：除文件及输入/出操作可使用库函数外，其他不允许使用库函数。
西安交通大学2001年数据结构试题
一、判断下列叙述是否正确，正确的填√，不正确的填×(10分) 1．数据对象就是一组数据元素的集合。 ( )
2．任何一棵前序线索二叉树，都可以不用栈实现前序遍历。 ( )
3．就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。 ( ) 4．用shell方法排序时，若关键字的排列杂乱无序，则效率最高。 ( ) 5．在m阶B-树中，所有非终端结点至少包含?m／2?。 ( ) 二、选择填空题(15分) 1．假设以数组A[m．．n]存放循环队列的元素，其头指针是front，当前队列有k个元素，则队列的尾指针为( )。
A．(front+k)mod(n-m+1) B．(m+k)mod n+front
C．(front-m+k)mod(n-m+1)+m D．(front-m+k)mod(n-m+1)
2． 已知二叉树如右图所示，此二叉树的顺 序存储的结点序列是( )。 A．123□45 B．12345 C．12□435 D．□24153
3．若用冒泡排序对关键字序列{20，17，11，8，6，2}从小到大进行排序，则需要交换的总次数为( )。 A．3 B．6 C．12 D．15
4．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是( )。 A．head=NULL B．head->next=NULL C．head->next==head D．head!=NULL 5．已知串s=“ABCDEFGH'’，则s的所有不同子串的个数为( )。 A．8 B．9 C．36 D．37 三、填空题(15分)
1．假设一个12阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素a8，9，在B中的存储位置k= 。
2．在拓扑排序中，拓扑序列的第一个顶点必定是 的顶点。
3．由六个分别带权值为5，12，9，30，7，16的叶子结点构造一棵哈夫曼(Huffinan)树，该树的结点个数为 ，树的带权路径长度为 。
4．在 的情况下，链队列的出队操作需要修改尾指针。
5．对表长为n的顺序表进行分块查找，若以顺序查找确定块，且每块长度为s，则在等概率查找的情况下，查找成功时的平均查找长度为 。 四、简答题(50分)
1．(6分)已知广义表L：((a，b)，(c，(d，(e)))，f)。
(1)试利用广义表取表头head(L)和取表尾tail(L)的基本运算，将原子c从下列广义表中分解出来，请写出运算表达式。
(2)请给出下列表达式的运算结果：
①hem(tail(head(tail(L)))) ②tail(tail(head(L))) 2．(10分)已知一个图G=(V，E)，其中：
V={a，b，c，d，e，f}；
E={
(2)根据邻接矩阵，分别同从顶点a出发的深度优先和广度优先遍历序列。 (3)画出由此得到的深度优先和广度优先生成树(或森林)。
3．(6分)已知一个栈s的输入序列为abcd，下面两个序列能否通过栈的PUSH和POP操作输出；如果能，请写出操作序列；如果不能，请说明原因。 ①dbca ②cbda
17
4．(5分)设模式串t=”abaabacababa”，试求出t的next和nextval函数值。
5．(7分)已知一组关键字K={20，15，4，18，9，6，25，12，3，22}，请判断此序列是否为堆?如果不是，请调整为堆。
6．(8分)对于表达式(a-b+c)*d/(e+f)
(1)画出它的中序二叉树，并标出该二叉树的前序线索； (2)给出它的前缀表达式和后缀表达式。
7．(8分)设散列长度为9，散列函数为H(k)=k mod 9，给出关键字序列：23，45，14，17，9，29，37，18，25，41，33，采用链地址法解决冲突。 (1)请画出散列表；
(2)求出查找各关键字的比较次数；
(3)计算在等概率情况下，查找成功的平均查找长度。
五、算法填空(10分)
已知图的邻接表存储结构描述如下： CONST N=图的顶点数： TYPE arcprt=↑arcnode； arcnode=RECORD adjvex：integer； nextarc：acrptr END；
vexnode=RECORD vexdata：char； firstarc：arcptr END；
Graph=ARRAY[1．．N]of vexnode；
下面是一个图的深度优先遍历的非递归算法，请在 处填上适当内容，使其成为一个完整算法。
PROCEDURE traver_dfs(g：graph)； VAR visited：ARRAY[1．．N] of BOOLEAN； s：STACK；{s为一个栈} p：arcptr： BEGIN
FORi：=1 TO N DO visited[i]：= ① INISTACK(S)； FOR i=1 TO N DO BEGIN ② BEGIN
visited[i]：=true；
visit(i)； //访问第i个顶点 IF g[i].firstarc≠NIL THEN PUSH(d，g[i].firstarc) END
WHILE ③ DO BECIN
p：POP(s)；
IF p↑.nextarc≠NIL THEN PUSH(s，p↑.nextarc)； j：=p↑.adjvex；
IF NOT visited[i] THEN BEGIN
visited[j]：=true； visit(j)；
IF e[j].firstarc≠NIL THEN ④
18
END END END END
中国科学院软件研究所2001年数据结构试题
一、单项选择题(每空2分，共20分)
1．下列函数中渐近时间复杂度最小的是( )。 A．T1(n)=nlog2n+5000n B．T2(n)=n2-8000n
C．T3(n)=nlog221-6000n D．T4(n)=2nlog2n-7000n
2．线性表的静态链表存储结构与顺序存储结构相比优点是( )。 A．所有的操作算法实现简单 B．便于随机存取 C．便于插入和删除
D．便于利用零散的存储器空间
3．设栈的输入序列为1，2，?，n，输出序列为a1，a2，?，an，若存在1≤k≤n使得ak=n，则当k≤i≤n时，ai为( )。
A．n-i+l B．n-(i-k) C．不确定
4．设高度为h的二叉树(根的层数为1)上只有度为0和度为2的节点，则此类二叉树中所包含的节点数至少为( )。
A．2h B．2h-1 C．2h+l D．h+l
5．设指针p指向线索树中的某个结点，则查找*p在某种次序下的前驱或后继不能获得加速的是( )。
A．前序线索树中查找*p的前序后继 B．中序线索树中查找*p的中序后继 C．中序线索树中查找*p的中序前继 D．后序线索树中查找*p的后序前继
6．假定有k个关键字互为同义词，若用线性探测法将这k个关键字存入散列表中，至少需要进行( )次探测。
A．k-1 B．k C．k+l D．k(k+1)/2
7．若待排序元素基本有序，则下列排序中平均速度最快的排序是( )；若要求辅助空间为O(1)，则平均速度最快的排序是( )；若要求排序是稳定的，且关键字为实数，则平均速度最快的排序是( )。
A．直接插入排序 B．直接选择排序 C．Shell排序 D．冒泡排序 E．快速排序 F．堆排序 C．归并排序 H．基数排序
8．对于多关键字而言，( )是一种方便而又高效的文件组织文式。 A．顺序文件 B．索引文件 C．散列文件 D．倒排文件 二、问答题(共25分)
1．设A[-2：6；-3：6]是一个用行主序存储的二维数组，已知A[-2，-3]的起始存储位置为loc(-2，-3)=1000，每个数组元素占用4个存储单元，求：(6分) 1)A[4，5]的起始存储位置loc(4，5)；
2)起始存储位置为1184的数组元素的下标。
2．给定二叉树的先序和后序遍历序列，能否重构出该二叉树?若能，试证明之，否则给出反例。(6分)
3．在含有n个关键字的m阶B-树中进行查找，至多读盘多少次?完全平衡的二叉排序树的读盘次数大约比它大多少倍?(设两种树中的每个节点均是一个存储块)。(8分)
4．用向量表示的循环队列的队首和队尾位置分别为1和max_size，试给出判断队列为空和为满的边界条件。(5分) 三、阅读程序题(共10分)
1．设G是一个有向无环图，试指出下述算法的功能，输出的序列是G的什么序列?(10分)
void Demo (ALGraph G)
{//G是图的逆邻接表，向量outdegree的各分量初值为0。
19
for(i=0；i for(p=G.adjlist[i].firstedge；p；p=p->next) //扫描i的入边表 outdegree[p->adjvex]++； //设p->adjvex=j，则将 j的出度加1 initStack(&s)； //设置空栈s for(i=0；i Push(&s，i)； //出度为0的顶点i入栈 while(!StackEmpty(s)) //栈s非空 { i=Pop(&Q)； //出栈，相当于删去顶点i prinft(“%c”，G.adjlist[i].vertex)；//输出顶点i for(p=G.adjlist[i].firstedge；p；p=p->next) { //扫描i的入边表 j=p->adjvex； //j是i的入边 outdegree[j]--； //j的出度减1，即删去i的入边 Push(&s?，j)； //若j的出度为0，则令其入栈 }//endfor }//endwhile }//endDemo 四、算法题(每题15分，共45分) 1．试设计算法在O(n)时间内将数组A[1．．n]划分为左右两个部分，使得左边的所有元素值均为奇数，右边的所有元素值均为偶数，要求所使用的辅助存储空间大小为O(1)。 2．试写一递归算法，从大到小输出二叉排序中所有的值不小于x的关键字，要求算法的时间为O(h+m)，其中h为树的高度，m为输出的关键字个数。 3．设G是以邻接表表示的无向图，v0是G中的一个顶点，k是一个正的常数。要求写一算法打印出图中所有与v0有简单路径相通，且路径长度小于等于k的所有顶点(不含v0)，路径长度由路径上的边数来定义。 参考答案 第一章 1．(a)是线性结构，对应的数据逻辑结构图见图1-2。 (b)是树形结构，对应的数据逻辑结构图见图1-3。 (c)是有向图，其数据逻辑结构图见图1-4。 2．(a)O(m×n) 2 (b)s+=b[i][j]的重复执行次数是n(n+1)／2，时间复杂度是O(n) (c)O(log2n) 3．D 4．D 5．D 第二章 一、单项选择题 (1) ～(5) DACAA (6)～(10) BAAAD 二、填空题 (1)链域 (2)插入 (3)删除 (4)n-i+1 (5)n-I (6)n／2 (7)(n-1)／2 (8)h=NULL (9)h->next=NULL (10)p->next=h (11) p->next->prior=s (12)p->next=s (13)p->prior->next (14)p->prior=s (15)p->next->prior=p (16)p->prior->next=p (17)p->next->prior=p->prior (18)r->next=p (19)r=p (20)r->next=q->next 三、应用题 1．顺序表：逻辑上相邻的数据元素其物理存储位置必须紧邻。其优点是：节省存储，可以随机存取。 链表：逻辑上相邻的数据元素其物理存储位置不要求紧邻，用指针来描述结点间的逻辑关系，故插入和删除运算比较方便。 2．在带表头结点的单链表中，头指针指向表头结点，不带表头结点的单链表中，头指针指向表 20