数据结构复习题(汇总)

《数据结构复习题(汇总)》由会员分享，可在线阅读，更多相关《数据结构复习题(汇总)（6页珍藏版）》请在金锄头文库上搜索。

1、第一套 （一）选择题 1.组成数据的基本单位（ ） A数据项 B.数据类型 C.数据元素 D.数据变量 2.快速排序最坏的时间复杂度（ ） AO(log2n) B.O(nlog2n) C.O(n) D.O(n2) 3.数组的逻辑结构不同于（ ） A线性表 B.栈 C.队列 D.树 4.二叉树第 i(i=1)层上的结点数最多有（ ） A2i B.2i C.2i-1 D.2i-1 5.设指针变量 P 指向单链表结点 A，删除 A 的后继 B 需（ ） Ap-next=p-next-next B.p=p-next C. p=p-next-next D.p-next=p6.若元素出列顺序为 E2,E4

2、,E3,E6,E5 和 E1，进栈 S 的容量至少应该是（ ） A6 B.4 C.3 D.2 7、将 10 阶对称矩阵压缩存储到一维数组 A 中，则数组 A 的长度最少为（） A100 B.40 C.55 D.80 8、设结点 A 有 3 个兄弟结点，且结点 B 为结点 A 的双亲结点，则结点 B 的读书为（） A.3 B.4 C.5 D.19、根据二叉树的定义可知二叉树共有（）种不同的形态 A.4 B.5 C.6 D.710、设有以下四种排序方法，则（）的空间复杂度最大 A.冒泡排序 B.快速排序 C.堆排序 D.希尔排序 （ 15 CDDCA 610 CCBBB）（二）填空 1、 设 一

3、组 初 始 记 录 关 键 字 序 列 为 （ 4 9,38,6 5,9 7,7 6,1 3,2 7,5 0） ， 则 以 d = 4为 增 量 的 一 趟 希 尔 排 序 结 束 后 的 结 果 为： （） 2、下面序段的功能是实现在二叉排序树中插入一个新结点，填空： Typedef struct node(int data; struct node *lchild; struct node *rchild;)bitree; void bstinsert (bitree * t-lchild=t-rchild=0; Else if (t-datak) Bstinser (t -lchild,

4、 k) else ( ) 3、 设指 针 变 量 P指 向 单 链 表 中 结 点 S， 指 针 变 量 S指 向 被 插 入 的 结 点 X， 则 在 结 点 A后 面 插 入 结 点 X需 要执 行 的 语 句 为： s n e x t = P - n e x t; (); 4、 设 指 针 变 量 h e a d指 向 双 向 链 表 中的 头 结 点， 指 针 变 量 P指 向 双 向 链 表 中 的 第 一 个 结 点， 则 指 针 变 量 P和 指 针 变 量 h e a d之 间 的 关 系是P =（） 和 head =（ ） （设结点中的指针域分别为 llink 和 rlink

5、 ） 5、 设 某 棵 二 叉 树 的 中 序 遍 历 序 列 为 ：A B C D， 后 序 遍 历 序 列 为 ：B A D C, 则 其前 序 遍 历 序 列 为： （） 6、完全二叉树中第 5 层上最少有（ ）个结点，最多有（ ）个结点； 7、 假 定 一 棵 树 的 广 义 表 表 示 为 A( C,D ( E,F , G), H ( I,J ) , 则 树 种 所 含 的 结点 数 为 9个， 树 的 深 度 为 （） ， 树 的 度 为 （） 。8、 设 一 组 初 始 记 录 关 键 字 序 列 为 （ 4 9,3 8,6 5,9 7,7 6,1 3,27,5 0） ， 则 第

6、 4趟 直 接 选 择 排 序 结 束 后 的 结 果 为： （） 9、 设 一 棵 完 全 二 叉 树 中 有 2 1个 结 点， 如 果 按 照从 上 到 下、 从 左 到 右 的 顺 序 从 1开 始 编 号， 则 编 号 为 8的 双 亲 结 点 的 编 号 为： （） ， 8的 做 孩 子 为 ： （） 10、 设 有 一 组 初 始 记 录 关 键 字 序 列 为 （ 5 0,1 6,2 3,6 8,9 4,7 0,7 3） ， 则 将 他 们 调 整 成 初 始 堆 只 需 把 1 6与 （） 相 互 交 换 即 可。答 案： 1、 4 9,1 3,2 7,5 0,7 6,3 8

7、,6 5,9 75、 C A B D6、 1； 1 67、 3； 38、3 8,4 9,6 5,9 7,7 6,1 3,2 7,5 09、 4； 1 41 0、 6 8(三)判断题 1.完全二叉树中的叶子结点只可能在最后两层中出现。 2.对链表进行插入和删除操作时需要依序移动链表中的结点。 3.子串“ABC”在主串“AABCABCD”中的位置为 2。 4.若 一 个 叶 子 结 点 是 某 二 叉 树 的 中序 遍 历 序 列 的 最 后 一 个 结 点， 则 它 必 是 二 叉 树 的 先 序 遍 历 序 列 中 的 最 后 一 个 结 点。5.希尔排序算法的时间复杂度为 O（n2） 。 6

8、.稀疏矩阵最后的压缩存储可以用一个三元组表来表示稀疏矩阵最后的非 0 元素。 7.中序遍历一棵二叉排序树可以得到一个有序的序列。 8.入栈操作和入队操作在链式存储结构上实现时需要考虑溢出的情况。 9.顺序表查找指的是手续存储结构上进行查找。 10. 堆是完全二叉树，完全二叉树不一定是堆。 答案：15 对错对对错 610 对对错错对（四）程序填空1.假定从键盘上输入一批整数，依次为：78 45 30 91 34 -1，请写出输出结果。 Const int stackmaxsize =30; Typedef int elemtype; Stuck stack elemtype stack stac

9、kmaxsize;int top; Void main() Stack a;Initstack(a);int x;cinx;while(x!=-1) push (a,x);cinx;while(!stackempty (a) count void Bintree; Unknown(BinTreeNode*t) BinTreeNode*p=t, *temp;If(p!=NULL)temp=p-leftchild;p-leftchild=p-rightchild;p-rightchild=temp;unknown(p-leftchild);unknown(p-rightchild); 该算法的功能

10、是：左右子树交换3.阅读下面的算法 Linklist mynote(Linklist L) /L 是不带头结点的单链表的头指针if (LL=L-next;p=L;S1:while(p-next) p=p-next;S2:p-next=q;q-next=NULL; return L 请回答下列的问题： 1） 说明语句 S1 的功能：把指针移动到链尾2） 说明语句组 S2 的功能：把头接到尾 3） 设链表表示的线性表为（a1,a2,an） ，写出算法执行后的返回值所表示的线性表： a2,a3,an,a14.已知二叉树的存储结构为二叉链表，阅读： Typedef struct node DataTy

11、pe data;Struct node *next; ListNode; Typedef ListNode *Linklist; LinkList Leafhead=NULL; Void Inorder (BinTree T) LinkList S;If(T) if(!T-lchild)S-data=T-data; S-next=Leafhead; Leafhead=S; Inorder(T-rchild); A对于二叉树BCDE FG H1）画出执行上述算法后建立的结果： 2）说明算法的功能：5.阅读下面算法： Void ABC (BTNode *BT) if (BT) ABC (BT-LE

12、FT);ABT (BT-right);Coutdatax) return 1; Else return 0; (1) 程序的功能是：判断 n 是否为素数（质数） (2) 时间复杂度：O（根号 n）2、阅读下面算法： Typedef int datatype; Typedef struct node datatype data ; struct node * next ; lklist; Void delredundant ( lklist * For( p=head ; p!=0 ; p= - next) For ( q=p - next ; s =q ; q!=0) If ( q - dat

13、a = p - data) S -next =q -next ; free ( q ); q=s - next ; Else s=q ; q=q - next ; 该算法的功能是： 在单链表中删除值相同的多余结点3、阅读下面算法： Void conversion( ) Stack s; int n ; SELemType e ; initstack ( s) ;Printf ( “pleade input number:”); Scanf ( “%d”, While (n) Push (s,n%8); n=n/8; While( ! stackempty ( s) Pop (s,e) ; printf ( “%d” , e); (1) 程序的功能是：将十进制转化为八进制 (2) 并给出一个测试用例（一个输入数据和一个输出结果）：10 ; 1,24、阅读下面算法： Int arrange ( int a , int l , int h , int x) / l 和 h 分别为数据区的下、上界Int i , j , t ;i=l; j=h;while ( i=x) j - - ；Which ( I x 的元素 均落在 a i+1,h 上。