山东理工大学数据结构期末试题及答案汇编

1、学习-好资料10-11学年 第一学期 计算机科学与技术专业张先伟、肖爱梅一、填空(每空1分，共20分)1、深度为k的完全二叉树至少有 可个结点，具有10个叶结点的二叉树中有 9个度为2的结点。2、 设数组a1.5,1.8的基地址为200，每个元素占2个存储单元，若以行序为主序顺序存储，则元素 a4,6的存储地址为 |200+(3*8+5)*2=258|。3、数据结构中评价算法的两个重要指标是时间复杂度和空间复杂度。4、顺序存储结构是通过元素在存储器中的相对位置表示元素之间的关系的；链式存储结构是通过指示| 元素存储地址的指针表示元素之间的关系的。5、 要在一个单链表中p所指结点之后插入一个子链

2、表，子链表第一个结点的地址为s,子链表最后一个 结点的地址为t,则应执行操作：t->next=p->next和 P->next=s。6、 设有向图G的存储结构用邻接矩阵 A来表示，则A中第i行中所有非零元素个数之和等于顶点i的 出度第i列中所有非零元素个数之和等于顶点i的入度。7、 对于表长为n的顺序存储的线性表，访问结点的时间复杂度为 丽，删除结点的时间复杂度为 丽。8、 将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点 编号为1,则编号最大的非叶结点的编号为：509、 己知有序表为(12，18，24，35, 47, 50，62, 8

3、3，90，115，134)，当用折半查找法查找 100时， 需3次才能确定不成功。10、Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按路径长度递增次序依次产生。11、 如果T2是由树T1转换而来的二叉树，那么T1中结点的后序遍历就是T2中结点的匝遍历。12、广义表 A= (d)则 Head(Tail(Head(Tail(Tail(A)的值为 d。13、 设无向连通图的顶点个数为 n,则该图最少有回条边，最多有|n(n-1)/2 |条边。二、选择(每题2分，共20分)1、 若需在O(nlog2n的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是CA. 快速排

4、序B.堆排序C.归并排序D.直接插入排序2、 有五个元素按5, 4, 3, 2, 1的顺序进栈，问下列哪一个不是合法的出栈序列？AA. 3 2 1 5 4B.4 5 3 1 2C.3 4 5 2 1D.2 3 4 1 53、无向图 G=(V,E)其中：V=a,b,c,d,e,f E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)对该图进行深度优先 遍历，得到的顶点序列正确的是 DA. a,b,e,c,d,f B. a,c,f,e,b,dC. a,e,b,c,f,dD. a,e,d,f,c,b4、链表不具有的特点是BA.插入、删除不需要移动元素B.可随机访问任

5、一元素学习-好资料C.不必事先估计存储空间D所需空间与线性表长度成正比5、 在一棵三叉树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，贝U度 为0的结点数为c个。A. 4B. 8C. 6D. 56、 若用一个大小为6的数组来实现循环队列，且当前 rear和front的值分别为0和3，当从队列中删除 一个元素，再加入两个元素后，rear和front的值分别是AA.2 和 4B.1 和 5C.4 和 2D.5 和 17、 若数据元素序列11，12，13，7, 8, 9, 23，4，5是采用下列排序方法之一得到的第二趟排序后的 结果，则该排序算法只能是BA.起泡排序B.插入排

6、序C选择排序D二路归并排序8、 对稀疏矩阵进行压缩存储目的是CA.便于进行矩阵运算B.便于输入和输出C.节省存储空间 D.降低运算的时间复杂度9、在下面的程序段中，对 x的赋值语句的频度为 Dfor ( i=1; i<= n; i+) for ( j=1; j<= n; j+) x=x+1;A. 0(2n)B. 0(n)C. 0(log2n)D. 0(n2)10、 双向链表中，在指针p指向的结点前插入指针q指向的结点的操作是CA. p->prior=q; q->next=p; p->prior->next=q; q->prior=qB. p->p

7、rior=q; p->prior->next=q; q->next=p; q->prior=p->prior;C. q->next=p; q->prior=p->prior; p->prior->next=q; p->prior=q;D. q->prior=p->prior; q->next=q; p->prior=q; p->prior=q;三、应用题(40分)1、(6分)已知一个无向图G=(V,E),其中V=A,B,C,D，E，F,邻接矩阵表示如下所示。P 1 0 1 0G =请回答下列问题：1

8、0 1110 0100011I00IQ0L0L01 I0010I(1) 请画出对应的图Go(2) 画出图G的邻接表存储结构学习-好资料2、（6 分）对于关键字序列（503, 87, 512, 61, 908, 120, 897, 275, 653, 462）,建立初始堆（小顶 堆）。3、（ 8分）已知一棵二叉树的先序序列： A B D H I M E J C F K L中序序列：H D I M B J E A K F L C请 画出该二叉树，并简单说明理由。4、 （ 6分）采用哈希函数H（k）=3*k MOD 13,并用线性探测开放地址法处理冲突，在数列地址空间0.12 中对关键字序列22、4

9、1、53、46、30、13、1、67、51,构造哈希表（画示意图）。5、（ 6分）下图为无向带权图，用克鲁斯卡尔算法构造其最小生成树，并写出选边的顺序。6、（ 8 分）对关键字序列30,15,28,20,24,10,12,68,35（1）构造一棵二叉排序树；（2）对初始序列构造一棵二叉平衡树。四、算法阅读与设计题（本大题共2小题，共20分）1、（8分）已知下列程序，Ls指向带头结点的单链表。Typedefstruct node DataType data; struct node * next; * LinkList;void f30（ LinkList Ls ） LinkList p, q;

10、q = Ls->next;if （ q && q->next ） Ls->next = q->next;p=qwhile （ p->next ） p = p->n ext;p->n ext = q; q->next = NULL;学习-好资料请回答下列问题:（1）当Ls指向的链表如下图所示，请画出执行本函数之后的链表的结果（2）请简述算法的功能。2、（ 12分）写出二叉树的二叉链表类型，设计算法求二叉树中度为1的结点的数目。（用自然语言给出设计思想，再用代码实现。06-07学年第二学期计算机科学与技术专业张先伟一 填空（每空1分，

11、共20分）1数据的存储结构主要有两类：储结构和储结构。2栈与队列都是限定性的数据结构，栈的操作特性是 ,队列的操作特性是。3. 在顺序表中插入或删除一个元素，需要平均移动 元素，具体移动的元素的个数与 有关。4. 组成串的数据兀素只能是 空串的长度是 °5. 广义表（a， （b）的深度是，表尾是。6. 深度为K的完全二叉树至少有 个结点，具有100个结点的完全二叉树的深度是 °7. N个定点的无向连通图至少有 条边，图的遍历有广度优先搜索遍历和 搜索遍历两种方法。&在一个单链表中在指针P所指结点之后插入一个S结点，应执行的操作依次是：S>next=和 P &g

12、t;next=。9. 影响哈希表查找长度的主要因素是_ 叩合希因子。10. 折半查找必须基于 储的 进行。二选择（每题2分，共20分）1一个带头结点的单链表，头指针为head,判断其是否为空的条件是 。A、head = NULLB head >next = NULLC、head != NULL;D、head >next = head更多精品文档2设栈的输入序列是1，2，3，4，则 可能是其输入序列A 1，2，4，3B、2，1，3，4C、4，3，1，2D、3，2，1，43. 稀疏矩阵的压缩存储不包含下面哪种方式 。A、三元组顺序表B行逻辑连接的顺序表C、邻接多重表D、十字链表4. 有

13、N个叶结点的哈夫曼树的结点总数是。A、不确定B、2NC、2N+1D、2N-15. 下列排序方法中，待排记录有序时花费时间反而最多的是 °A、快速排序B、希尔排序C、6. 下面有关二叉树的说法正确的是 A、二叉树的度为2C、二叉树中至少有一个节点的度数为 27. 堆的形状是一棵。A、二叉排序树 B、满二叉树C、8、关键路径是 AOE网中。A、从源点到汇点的最长路径C、从源点到汇点的最短路径9、 循环队列是空队列的条件是°起泡排序D、堆排序B、二叉树的度可以小于 2D、二叉树中任何一个结点的度数都为 2完全二叉树D、平衡二叉树B、从源点到汇点的最长回路D、从源点到汇点的最短回路

14、学习-好资料A、Q >rear = Q- >frontB、（Q >rear+1） %maxsize = >frontC、Q >rear = 0D、Q >front = 010、在有向图G的拓扑排序序列中，若定点 Vi在顶点Vj之前，贝U下列情形不可能出现的是 ，A、G中有弧<Vi, Vj>B、G中有一条从Vi到Vj的路径C、G中没有弧<Vi, Vj>D、G中有一条从Vj到Vi的路径三、问答与综合（共5个题目，36分）1、（6分）什么是数据的逻辑结构？简述常见的逻辑结构的分类及其特点。2、（8分）已知二叉树，其中序序列 DBCAFGE后

15、序序列DCBGFEA（1）构造该二叉树，并简单说明理由；（2）将该二叉树转换成相应的树（或森林）。3、（8分）对于如下的无向网（1）写出其邻接表；（2）按照Prime算法求网的一棵最小生成树（写出过程）4、（8分）对下面的二叉排序树:23更多精品文档学习 好资料更多精品文档1）求二叉排序树在等概率查找时平均查找长度；2）画出插入关键码 16 后的结果；3）画出对原树删除关键码 40 后的结果。5、（6 分）初始关键字序列为（ 30，4，28，58， 5，13，90，47，18） （1）写出对其做一趟直接插入排序后的结果； （2）对其初始序列以 30 为枢轴做一次快速排序后的结果。h 是带头结点的单链表的头指四、算法阅读（共两个题目， 12 分）1、阅读下面算法，说明该算法的功能，并分析其时间复杂度(已知 针)Void rever( lnode *h) lnode p,q;p = h->next; h->next = null; while( p) q = p;p = p->next;q->next = h->next; h->next = q; /end while /end rever2、下面是折半查找算法，在 处将算法语句补充完整。int Search (