南京信息工程大学滨江学院数据结构期末试题及答案

. 一、单项选择题 1、在以下的叙述中，正确的是( A )。 A.线性表的线性存储结构优于链表存储结构 B.二维数组是其数据元素为线性表的线性表 C.栈的操作方式是先进先出 D.队列的操作方式是先进后出 2、判定一个循环队列qu(最多元素为m0)为空的条件是( A )。 A. qu-front==qu-rear B. qu-front!=qu-rear C. qu-front=(qu-rear+1)%m0 D. qu-front!=(qu-rear+1)%m0 3、 向一个栈顶指针为hs的链栈中插入一个s所指结点时， 则执行( C )。 A. hs-next=s; B. s-next=hs-next;hs-next=s; C. s-next=hs;hs=s; D. s-next=hs;hs=sh-next 4、串是一种特殊的线性表，其特殊性体现在（ B）。 A.可以顺序存储 B.数据元素是一个字符 C.可以链接存储 D.数据元素可以是多个字符 5、设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存 放在一维数组B[1,n(n-1)/2]中，对下三角部分中任一元素ai,j(i≥j),在 一维数组B的下标位置k的值是（ B ）。 A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j 6、将递归算法转换成对应的非递归算法时，通常需要使用( A )。 . . A.栈 B.队列 C.链表 D.树 7、 树的基本遍历策略可分为先根遍历和后根遍历叉树的基本遍历策略可 分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二 叉树叫做这棵树对应的二叉树。结论__A__是正确的。 A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D. 以下都不对 8、对一个满二叉树，m个树叶，n个结点，深度为h，则( D )。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2h-1 9、具有7个顶点的无向图至少应有(A )条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 10、判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可 以利用( D )。 A.求关键路径的方法 B.求最短路径的Dijkstra方法 C.宽度优先遍历算法 D.深度优先遍历算法 11、 有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分 查找值为82的结点时，( C )次比较后查找成功。 A. 1 B. 2 C. 4 D. 8 12、如果要求一个线性表既能较快地查找，又能适应动态变化的要求， 可以采用___A__查找方法。 A.分块 B.顺序 C.二分 D.散列 13、在所有排序方法中，关键字比较的次数与记录的初始排列次序无关 的是____D_____。 A.希尔排序 B.起泡排序 C.插入排序 D.选择排序 . . 14、快速排序方法在( C )情况下最不利于发挥其长处。 A.要排序的数据量太大 B.要排序的数据中含有多个相同值 C.要排序的数据已基本有序 D.要排序的数据个数为奇数 15、索引无序文件是指( A )。 A.主文件无序，索引表有序 B.主文件有序，索引表无序 C. 主文件有序，索引表有序 D.主文件无序，索引表无序 二、填空题（每空二、填空题（每空 2 2 分，共分，共 30 30 分）分） 16、下面程序段的时间复杂度是___O(m*n)____。 for ( i=0;idata=x;s=p;_。 18 、 在 hq 的 链 队 中 ， 判 定 只 有 一 个 结 点 的 条 件 是 __hq-front=hq-rear__。 19、已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储 单元，并且第一个元素的存储地址是 LOC(A[0][0])，A[i][j]的地址是 ___LOC(A[0][0])+(n*i+j)*k___。 20、有如下递归方程： void print(int w) { int i; if (w!=0) . . { print(w-1); for (i=1;iv2-v3-v6-v5-v4_，其从顶点v1出发的宽度优先搜索序列为 _v1-v2-v5-v4-v3-v6_。 24、在各种查找中，平均查找长度与结点个数n无关的查法方法是_哈希 ___。 . . 25、 在对一组记录{54,38,96,23,15,72,60,45,83}进行直接插入排序时， 当把第 7 个记录 60 插入到有序表时，为寻找插入位置需比较_3_次。 26、顺序查找法的平均查找长度为__n(n+1)/2_____；二分查找法的平均 查找长度为___((n+1)*log2(n+1))/n-1____。 三、解答操作题（每小题三、解答操作题（每小题 5 5 分，共分，共 20 20 分）分） 27、已知序列{503,87,512,61,908,170,897,275,653,462},采用基数排 序法对该序列作升序排序时的每趟的结果。 A[0]=170 A[1]=61 A[2]=512-462 A[3]=503-653 A[5]=275 A[7]=87-897 A[8]=908 28、设给定权集w={2,3,4,7,8,9},度构造关于w的一棵哈夫曼树，并求其 加权路径长度wpl。 29、对下图所示的树： (1)转换成对应的二叉树形式，并且说明转换规则； (2)写出前序、中序、后序遍历的结果； . . 30.现有稀疏矩阵 A 如下图所示，要求画出以下几种表示法。 （1）三元组表示法 （2）带行指针向量的单链表表示法 （3）十字链表示法。 四、算法阅读题四、算法阅读题 ( (每小题每小题6 6分，共分，共1212 分分) ) 31、下列算法的功能是实S串的逆序 (串均采用顺序存储方式)，请在空白处填入适当的内容。 SeqString *invert (SegString *s) { int i; char temp for (i=0; ilength/2; i++) { temp=s-ch[i]; s-ch[i]=s-ch[ s-length-i+1 ]; s-ch[s-length-i+1]= temp ; } return s ;} 32.下列算法的功能是实现链栈的进栈运算，请在空白处填入适当的内 容。 链栈的类型定义如下： Typedef struct stacknode { DataType data; Struct stacknode *next; } StackNode; Typedef struct { StackNode *top; . . }LinkStack; Void Push(LinkStack *s,DataType x) { StackNode p; *p=(Stack