数据结构期末考试题26


班密 级 :
封 装 订 线

4.某带头结点的单链表的头指针 head,判定该单链表非空的条件________________。 5. 在序列(2,5,8,11,15,16,22,24,27,35,50)中采用折半查找(二分查找)方法查找元素 24,需要进行

专业: 姓名: 考号:

信息技术学院 2006-2007 学年第二学期期末考试 数据结构 试卷 26(适用班级: )
(答题时间:120 分钟,满分:100 分)
题 得 号 分 第一部分 第二部分 第三部分 第四部分 总 分 核分人

______________次元素之间的比较。 6.对关键字序列(50,34,92,19,11,68,56,41,79)进行直接插入排序,当将第 7 个关 键字 56 插入到当前的有序子表中,为寻找插入位置需进行________次比较。 7.如果从一个顶点出发又回到该顶点,则此路径叫做_______。 得 分

评卷人

三、选择题: (共 20 分,每题 2 分)
得 分 1. 二维数组 A 按行顺序存储,其中每个元素占 1 个存储单元。若 A[1][1]的存储地址为 420, A[3][3]的存储地址为 446,则 A[5][5]的存储地址为_______

评卷人

一、判断: (共 10 分,每题 1 分, )


A.470

B.471

C.472 D.473 2.线性表若采用链表存储结构时,要求内存中可用存储单元的地址_________ 2.单链表形式的队列,头指针 F 指向队列的头结点,尾指针 R 指向队列的尾结点。 ( ) A.必须是连续的 B.部分地址必须是连续的 3.队列是一种插入和删除操作在表的一端进行的线性表。 ( ) C.一定是不连续的 D.连续不连续都可以 4.若频繁地对线性表进行插入和删除操作,该线性表采用链式存储结构更合适。 ( ) 3.下面程序段的时间复杂度为____________ for(int i=0; i<m; i++) 5.稀疏矩阵中 0 元素的分布有规律,因此可以采用三元组方法进行压缩存储。 ( ) for(int j=0; j<n; j++) 6.若线性表采用顺序存储结构, 每个数据元素占用 4 个存储单元, 12 个数据元素的存储 第 a[i][j]=i*j; 2 2 A.O(m ) B.O(n ) C.O(m*n) D.O(m+n) 地址为 144,则第 1 个数据元素的存储地址是 101。 ( ) 4.队和栈的主要区别是___________ 7.如果一个串中的所有字符均在另一串中出现,则说前者一定是后者的子串。 ( ) A.逻辑结构不同 B.存储结构不同 8.数组是向量推广。 ( ) C.所包含的运算个数不同 D.限定插入和删除的位置不同 9.将一棵树转换成二叉树后,根结点没有左子树; ( ) 5.一个非空广义表的表头_________ 10.哈希表的查找无需进行关键字的比较。 ( ) A.不可能是子表 B.只能是子表 C.只能是原子 D.可以是子表或原子 得 分 6.假定一个顺序队列的队首和队尾指针分别为 front 和 rear,存放该队列的数 组长度为 N,则判断队空的条件为________ 评卷人 A.(front+1)% N == rear B. (rear+1)% N == front C. front == rear D. front == 0 二、填空: (共 20 分,每空 2 分, ) 7.在一个单链表 HL 中,若要向表头后插入一个由指针 p 指向的结点,则执行 ________ A.HL = p;p->next = HL; B.p->next = HL;HL = p; 1.线性表可以在 _______位置进行插入,栈可以在_____位置进行插入,队列可以在_____ C.p->next = HL;p = HL; D.p->next = HL->next;HL->next = p; 位置进行插入。 2.在非空线性表中除第一个元素外,集合中每个数据元素只有一个_________;除最后一个 8.在目标串 T[0…n-1]=‘xwxxyxy’中,对模式串 p[0…m-1]=‘xy’进行子串定位操作的 结果___________ 元素之外,集合中每个数据元素均只有一个__________。 A.0 B.2 C.3 D.5 3.在栈的顺序实现中,栈顶指针 top,栈为空条件______________。 第 1 页 共 3 页 1.字符串是一种非线性结构。 (

9.如果某图的邻接矩阵是对角线元素均为零的上三角矩阵,则此图是_______ A.有向完全图 C.强连通图 B.连通图 D.有向无环图

10.由权值分别为 3,8,6,2,5 的叶子结点生成一棵哈夫曼树,它的带权路径长度为________。 A、 24 C、 72 B、 48 D、 53 3、考虑下图: (1)顶点 A 出发,求它的深度优先生成树。 (2)从顶点 A 出发,求它的广度优先生成树。 (3)根据普里姆算法,求它的最小生成树。 (共 12 分) 得 分

评卷人

四、应用题(30 分) :
1.已知稀疏矩阵如下:请写出该稀疏矩阵三元组表示。 分) (6





评卷人

4. 设一棵二叉树的层序序列是 ABCDEFGHIJ 和中序序列是 DBGEHJACIF,请画出该二叉树。 6 ( 2. 序列(46,88,45,39,70,58,101,10,66,34)建立一个二叉排序树,画出该二叉树, 分) 并求在等概率情况下查找成功的平均查找长度。(6 分)

五.程序题(20 分)
1、算法填空: (每空 2 分,共 8 分) 第 2 页 共 3 页

完成二叉树按层遍历的算法。 Void leveltravel ( struct treenode *bt) { struct treenode *p,*a[n]; int rear=front = -1; p=bt; rear =__________; a[rear]=p; while (rear != front) { front = ___________; p=a[front]; printf(“%c”,p->data); If ( p->left !=null) { rear =(rear +1)% n a[rear]= _________; } If (p->right!= null) {rear = (rear +1)%n ; a[rear]=_________; } } }

else {for (j=i-1;j<n;j++) a[j]=a[j+1]; n=n-1;} }

2、阅读下列算法,并回答下列问题: 分) (8 完善程序,并回答该算法完成什么功能?算法中 r[n+1]的作用是什么? void sort (elemtype r[],int n) {int k,i; for(k=n-1;k>=1;k- -) if(r[k]>r[k+1]) { r[n+1]=r[k]; for(i=k+1;r[i]<r[n+1];i++) r[i-1]=r[i]; ;} }}

3. 说出下面算法完成的功能。(4 分) void delete( int a[n],int i) {if (i<0)||(i>=n) printf(“error”); 第 3 页 共 3 页


相关文档

更多相关文档

数据结构期末考试题
数据结构 期末考试题2
06级数据结构期末考试题
数据结构期末考试题04~05
数据结构 期末考试题
2012年数据结构期末考试题及答案
2012年数据结构期末考试题及答案 2
数据结构期末考试题04~05(2)
河北大学数据结构期末考试题
数据结构期中考试
数据结构期末考试题04~05(2)
数据结构期末考试题28
数据结构期末考试题30
《数据结构》期末考试题及答案
数据结构试题及答案
电脑版