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

《南京信息工程大学滨江学院数据结构期末试题及答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、单项选择题1、在以下的叙述中，正确的是(A)。A.线性表的线性存储结构优于链表存储结构B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出2、判定一个循环队列qu(最多元素为m0)为空的条件是(A)。A.qu->front==qu->rearB.qu->front!=qu->rearC.qu->front=(qu->rear+1)%m0D.qu->front!=(qu->rear+1)%m03、向一个栈顶指针为hs的链栈中插入一个s所指结点时，则执行(C)。A.hs->next=s;B.s->next=hs-

2、>next;hs->next=s;C.s->next=hs;hs=s;D.s->next=hs;hs=sh->next4、串是一种特殊的线性表，其特殊性体现在（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-1B.i(i-1)/2+jC.i(i+1)/2+j-1D.i(i+1)/2+j6、将递归算法转换成对应

3、的非递归算法时，通常需要使用(A)。第8页(共8页)A.栈B.队列C.链表D.树7、树的基本遍历策略可分为先根遍历和后根遍历叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论__A__是正确的。A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D.以下都不对8、对一个满二叉树，m个树叶，n个结点，深度为h，则(D)。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-19、具

4、有7个顶点的无向图至少应有(A)条边才能确保是一个连通图。A.5B.6C.7D.810、判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用(D)。A.求关键路径的方法B.求最短路径的Dijkstra方法C.宽度优先遍历算法D.深度优先遍历算法11、有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时，(C)次比较后查找成功。A.1B.2C.4D.812、如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用___A__查找方法。A.分块B.顺序C.二分D.散列13

5、、在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是____D_____。A.希尔排序B.起泡排序C.插入排序D.选择排序第8页(共8页)14、快速排序方法在(C)情况下最不利于发挥其长处。A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据已基本有序D.要排序的数据个数为奇数15、索引无序文件是指(A)。A.主文件无序，索引表有序B.主文件有序，索引表无序C.主文件有序，索引表有序D.主文件无序，索引表无序二、填空题（每空2分，共30分）16、下面程序段的时间复杂度是___O(m*n)____。for(i=0;i

6、+)for(j=0;jnext=s;p->data=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、有如下递归方程：voidprint(intw){inti;if(w!=0){print(w-1);第8页(共8页)

7、for(i=1;i<=w;i++)print(“%3d”,w);rpintf(“/n”);}}调用语句print(4)结果是___1223334444_____21、广义表(a,(a,b),d,e,((i,j),k))的长度是___5_____，深度是__3___。22、以数据集{4,5,6,7,10,12,18}为结点权值所构造的哈夫曼树为_____，其带权路径长度为________。23、已知图G的邻接表如下图所示，其从顶点v1出发的深度优先搜索序列为_v1->v2->v3->v6->v5->v4_，其从顶点v1出发的宽度优先搜索序列为_v1->v2

8、->v5->v4->v3->v6_。24、在各种查找中，平均查找长度与结点个数n