数据结构试题集与答案汇总

数据结构

需积分: 9 170 浏览量更新于2024-07-20 收藏 654KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

数据结构试卷（三）

一、选择题(每题 1 分，共 20 分)

1 ．设某数据结构的二元组形式表示为

A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01

，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据

结构 A 是（ B ）。

(A) 线性结构 (B) 树型结构 (C) 物理结构 (D) 图型结构

2．下面程序的时间复杂为（ B ）

for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；}

(A) O(n) (B) O(n

) (C) O(n

) (D) O(n

)

3．设指针变量 p 指向单链表中结点 A，若删除单链表中结点 A，则需要修改指针的操作序

列为（ A ）。

(A) q=p->next；p->data=q->data；p->next=q->next；free(q)；

(B) q=p->next；q->data=p->data；p->next=q->next；free(q)；

(D) q=p->next；p->data=q->data；free(q)；

4．设有 n 个待排序的记录关键字，则在堆排序中需要（ A ）个辅助记录单元。

(A) 1 (B) n (C) nlog

n (D) n

5．设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以 20 为

基准记录的一趟快速排序结束后的结果为( A )。

(A) 10，15，14，18，20，36，40，21

(B) 10，15，14，18，20，40，36，21

(D) 15，10，14，18，20，36，40，21

6．设二叉排序树中有 n 个结点，则在二叉排序树的平均平均查找长度为（ B ）。

(A) O(1) (B) O(log

n) (C) (D) O(n

)

7．设无向图 G 中有 n 个顶点 e 条边，则其对应的邻接表中的表头结点和表结点的个数分别

为（ D ）。

(A) n，e (B) e，n (C) 2n，e (D) n，2e

8. 设某强连通图中有 n 个顶点，则该强连通图中至少有（ C ）条边。

(A) n(n-1) (B) n+1 (C) n (D) n(n+1)

9．设有 5000 个待排序的记录关键字，如果需要用最快的方法选出其中最小的 10 个记录

关键字，则用下列（ B ）方法可以达到此目的。

(A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 插入排序

10.下列四种排序中（ D ）的空间复杂度最大。

(A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 归并排序

二、填空殖(每空 1 分共 20 分)

1. 数据的物理结构主要包括_____________和______________两种情况。

2. 设一棵完全二叉树中有 500 个结点，则该二叉树的深度为__________；若用二叉链表

作为该完全二叉树的存储结构，则共有___________个空指针域。

3. 设输入序列为 1、2、3，则经过栈的作用后可以得到___________种不同的输出序列。

4. 设有向图 G 用邻接矩阵 A[n][n]作为存储结构，则该邻接矩阵中第 i 行上所有元素之和

等于顶点 i 的________，第 i 列上所有元素之和等于顶点 i 的________。

5. 设哈夫曼树中共有 n 个结点，则该哈夫曼树中有________个度数为 1 的结点。

6. 设有向图 G 中有 n 个顶点 e 条有向边，所有的顶点入度数之和为 d，则 e 和 d 的关系

为_________。

7. __________遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序

或后序）。

8. 设查找表中有 100 个元素，如果用二分法查找方法查找数据元素 X，则最多需要比较

________次就可以断定数据元素 X 是否在查找表中。

9. 不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均

为____________。

10. 设有 n 个结点的完全二叉树，如果按照从自上到下、从左到右从 1 开始顺序编号，则

第 i 个结点的双亲结点编号为____________，右孩子结点的编号为___________。

11. 设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字 72 为

基准的一趟快速排序结果为___________________________。

12. 设有向图 G 中有向边的集合 E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该

图的一种拓扑序列为____________________。

13. 下列算法实现在顺序散列表中查找值为 x 的关键字，请在下划线处填上正确的语句。

struct record{int key; int others;};

int hashsqsearch(struct record hashtable[ ],int k)

{

int i,j; j=i=k % p;

while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1);}

if (_______________________ ) return(j); else return(-1);

}

14. 下列算法实现在二叉排序树上查找关键值 k，请在下划线处填上正确的语句。

typedef struct node{int key; struct node *lchild; struct node *rchild;}bitree;

bitree *bstsearch(bitree *t, int k)

{

if (t==0 ) return(0);else while (t!=0)

if (t->key==k)_____________; else if (t->key>k) t=t->lchild; else_____________;

}

三、计算题(每题 10 分，共 30 分)

1.已知二叉树的前序遍历序列是 AEFBGCDHIKJ，中序遍历序列是 EFAGBCHKIJD，画出

此二叉树，并画出它的后序线索二叉树。

2．已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为 [0..6]，假

定选用的散列函数是 H（K）= K mod 7，若发生冲突采用线性探查法处理，试：

（1）计算出每一个元素的散列地址并在下图中填写出散列表：

` 0 1 2 3 4 5 6

（2）求出在查找每一个元素概率相等情况下的平均查找长度。

3．已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。

四、算法设计题(每题 15 分，共 30 分)

剩余42页未读，继续阅读

dream_113

粉丝: 1
资源: 33

数据结构试题集与答案汇总

数据结构1800题及答案_pdf.zip

目前最完整的数据结构1800题内含完整答案（考研专用）

数据结构试题全集题库.doc

数据结构试题答案csdn

noc初赛试题及答案

清华大学数据结构答案

csp_j复赛试题及答案

北理工数据结构小学期试题

大一c语言期末考试试题及答案汇总

研究生复试c语言试题及答案

cspj2021初赛试题无答案

2020csp-j入门级第一轮试题及参考答案.pdf

山东大学2019年-数据结构-期末试卷真题.pdf

csp-j+csp-s新题型初赛模拟试题附答案

【职业技能大赛计算机程序设计员赛项】理论试题及参考答案.pdf

nudt计算机体系结构试题

说一些常见的生命科学与其他学科交叉创新的综合开放性试题及答案

pandas试题答案

最新资源