大学考试《数据结构与算法分析》试卷A1

《大学考试《数据结构与算法分析》试卷A1》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一、选择题(每小题2分，共20分)得分:1.在下面的程序段中，对x的赋值语句的频度为(for(i二1;i<=n;i++)for(j=l;j<=n;j++)A.0(2n)B.O(n)C.0(n2)D.0(log2n)2•线性表采用链式存储时，其地址(A.一定不连续B.连续与否均可以C.一定连续D.部分地址必须是连续的3.发牛非法操作时，算法能够作出适当处理的特性称为(A.可读性B.健壮性C.止确性D.可移植性4.由下列三棵树组成的森林换成一棵二叉树为(A.'/⑧/©B.C.©/•®/-⑧©5.具有

2、100个结点的完全二叉树的深度为(©©A.6B.7C.8D.®©/©⑥z®/©'©D.96•已知一个6X6的稀疏矩阵，其三元组表如下：(1,2,3),(1,6,1),(3,1,5),(3,2,-1),(4,5,4),(5,1,-3),则其转置矩阵的三元组表中第3个三元组为（）A.(2,1,3)B.(3,1,5)C.(3,2,-1)D.(2,3,-1)7.无向图的邻接矩阵是一个（)A.对称矩阵B.零矩阵0上=角矩阵D.对角矩阵&下列说法屮正确的是（）A.一个具有n个顶点的无向完全图的边数为n（

3、n-1）B.连通图的生成树是该图的一个极大连通子图C.图的广度优先搜索是一个递归过程D.对于非连通图的遍历过程中每调用一次深度优先搜索算法都得到该图的一个连通分量9•一组记录的关键码为（46,79,56,38,40,84）,则利用快速排序方法，以第一个记录为基准得到的一次划分结果为（）B.40,38,46,79,56,84D.40,38,46,84,56,79)10)B.仃0,5,8,4,2,6,7,1,3)D.(1,2,3,4,10,9,8,7,6,5)A.38,40,46,56,79,84C.

4、40,38,46,56,79,8410.下列序列屮，不构成堆的是(A.仃，2,5,3,4,6,7,8,9,C.（10,9,8,7,3,5,4,6,2）得分：分二、填空题（每空2分，共30分）1.数据的逻辑结构通常包括集合、线性结构、和图状结构。2.表示逻辑关系的存储结构可以有四种方式，即、链式存储方式、索引存储方式和散列存储方式。3.设某非空单链表，其结点形式为datenext若要删除指针q所指结点的直接后继结点，则需执行下列语句序列：p=q->next;;free（p）;4.队列中允许进行删除的

5、一端为4.如图所示，设输入元素的顺序是A,B,C,D,通过栈的变换，在输出端可得到各种排列。若输出序列的第一个元素为D,则输出序列为ARCD<—-输川端输入端栈4.设T和P是两个给定的串，在T中寻找等于P的子串的过程称为o7•在非空树上，没有直接前趋。8.设有33个值，用它们组成一棵哈夫曼树，则该哈夫曼树中共有个结点。9•设一棵二叉树中度为2的结点数为10,则该树的叶子数为o10.在一棵二叉排序树上按遍历得到的结点序列是一个有序序列。11•下列算法在有序表r中插入元素x,并保持表r的有序性，其中参

6、数n++;}三、解答题(每题6分，共30分)1.循环队列的优点是什么？进队和岀队吋如何修改队尾和队头指针?n为表r的长度，算法中查找插入位置的方法使用折半查找法。请在空缺处填入合适的内容，使其成为一个完整的算法。voidBininsort(ScqListr,int*n,DateiTypcx){int1ow=1,high二*n,mid,i;while(low<=high){mid=;if(x.key>r[mid]・key)1ow=;elsehigh二；}得分：分for(i=*n;i>=hight+l

7、;i—)2.已知一棵二叉树如图所示，分别写出对该二叉树进行先序遍历和中序遍历的序列。先序序列:中序序列:1.假设通信电文使用的字符集为{a,b,c,d,e,f},各字符在电文中出现的频度分别为：34,5,12,23,8,18,试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树（要求树中左孩子结点的权值小于右孩子结点的权值），然后分别写出每个字符对应的编码。2.已知有向图G的定义如下:G=(V,E)V={a,b,c,d,c}E二{〈a,b>,〈a,c>,,,,

8、,c>,}(1)画出G的图形;(2)写岀G的两个拓扑序列。5•假定采用II(k)=k%7计算散列地址，利用开放定址法屮的线性探测法解决冲突，试在0〜6的散列地址空间中，对关键字序列(38,25,74,63,52,48)构造散列表，并求出等概率情况下查找成功的平均查找长度ASL。四、设计题(每题10分，共20分)得分：分1.设单链表的结点结构如下：structnode{datatypedata;struetnode*next;};试编写一个函数intcount(struct