tceic.com
简单学习网 让学习变简单
相关标签
当前位置:首页 >> 其它课程 >>

数据结构((本)期末综合练习(2012年12月)


数据结构期末综合练习 2012 年 12 月 期末练习一 一、单项选择题 1. 一种逻辑结构在存储时( ) 。 A.只要存储数据元素间的关系 B.只能采用一种存储结构 C.可采用不同的存储结构 D.只要存储数据元素的值 2.同一种逻辑结构( ) 。 A.只能有唯一的存储结构 B.可以有不同的存储结构 C.只能表示某一种数据元素之间的关系 D.以上三种说法均不正确 3 .对链表,

以下叙述中正确的是( ) 。 A.不能随机访问任一结点 B.结点占用的存储空间是连续的 C.插入删除元素的操作一定要要移动结点 D.可以通过下标对链表进行直接访问 4.链表所具备的特点是( ) 。 A.可以随机访问任一结点 B.占用连续的存储空间 C.插入删除元素的操作不需要移动元素结点 D.可以通过下标对链表进行直接访问 5.线性表在存储后,如果相关操作是:要求已知第 i 个结点的位置访问该结点的前驱结点,则 采用( )存储方式是不可行的。 A.单链表 B.双链表 C.单循环链表 D.顺序表 6.数据的物理结构( ) 。 A.与数据的逻辑结构无关 B.仅仅包括数据元素的表示 C.只包括数据元素间关系的表示 D.包括数据元素的表示和关系的表示 7.栈和队列的共同特点是( ) 。 A.都是先进后出 B.元素都可以随机进出 C.只容许在端点处插入和删除元素 D.都是先进先出 8.线性结构中数据元素的位置之间存在( )的关系。 A.一对一 B.一对多 9.元素 2,4,6,8 按顺序依次进栈,按该栈的的可能输出序列依次入队列,该队列的可能 输出序列是( ) (进栈出栈可以交替进行) 。 A.8,6,2,4 B.8,4,2,6 C.6,2,4,8 D.8,6,4,2 10.以下表中可以随机访问的是( ) 。 A.单向链表 B.双向链表 C.单向循环链表 D.顺序表 11.在一个不带头结点的链队中,假设 f 和 r 分别为队头和队尾指针,则从该对列中删除一 个结点并把结点的值保存在变量 x 中的运算为( ) 。 A.x=r?data;r=r?next; B.r=r?next; x=r?data C.x=f?data;f=f?next; D.f=f?next; x=f?data 12.算法的时间复杂度与( )有关。 A.所使用的计算机 B.与计算机的操作系统 C.与算法本身 D.与数据结构 13.设有一个 20 阶的对称矩阵 A,采用压缩存储的方式,将其下三角部分以行序为主序存储

1

到一维数组 B 中(数组下标从 1 开始) ,则数组中第 38 号元素对应于矩阵中的元素是 ( ) 。 A.a10,8 B.a7,6 C.a9,2 D.a8,5 14.设有一个长度为 n 的顺序表,要删除第 i 个元素需移动元素的个数为( ) 。 A.n-i+1 B.n-i C.n-i-1 D.i 15.在 C 语言中,分别存储 “S”和‘s’,各需要占用( )字节。 A.一个和两个 B.两个 C.一个 D.两个和一个 16.在一个单链表中,p、q 分别指向表中两个相邻的结点,且 q 所指结点是 p 所指结点的直 接后继,现要删除 q 所指结点,可用的语句是( ) 。 A.p=q->next B.p->next=q C.p->next=q?next D.q->next=NULL 17.一棵有 n 个结点,采用链式存储的二叉树中,共有( )个指针域被有效使用(即指 针域为非空) 。 A.n+1 B.n C.n-1 D.n-2 18.从一个栈顶指针为 top 的链栈中删除一个结点时,用变量 x 保存被删结点的值,则执行 ( ) 。 A.x=top->data; top=top->next; B.x=top->data; C.top=top->next; x=top->data; D.top=top->next; x=data; 19.在一棵二叉树中,若编号为 i 的结点存在双亲结点,则双亲结点的顺序编号为( ) 。 A.i/2.0 B.i/2 向下取整 C.2i+1 D.i+2 20.在一个链队中,假设 f 和 r 分别为队头和队尾指针,则删除一个结点的运算为( ) 。 A.r=f->next; B.r=r->next; C.f=f->next; D.f=r->next; 21.设一棵哈夫曼树共有 2n+1 个结点,则该树有( )个非叶结点。 A.n B.n+1 C.n-1 D.2n 22.一个栈的进栈序列是 a,b,c,d,e,则栈的不可能输出序列是( ) (进栈出栈可以 交替进行) 。 A.dceab B.edcba C.decba D.abcde 23.一棵完全二叉树共有 4 层,且第 4 层上有 2 个结点,该树共有( )个非叶子结点 (根为第一层)。 A.5 B.4 C.3 D.9 24.有一个长度为 10 的有序表,按折半查找对该表进行查找,在等概率情况下查找成功的平 均比较次数为( ) 。 A.26/10 B.29/10 C.29/9 D.31/10 25.如图 1 所示的一个图,若从顶点 a 出发,按广度优先搜索法进行遍历,则可能得到的一 种顶点序列为( ) 。 A.abedfc B.acfebd C.aebcdf D.aebcfd a b

e

c

d

f

2

图1 26.排序算法中,从未排序序列中依次取出元素与已排序序列(初始为空)中的元素进行比 较(要求比较次数尽量少) ,然后将其放入已排序序列的正确位置的方法是( ) 。 A.冒泡 B.直接插入 C.折半插入 D.选择排序 27.一组记录的关键字序列为(56,30,89,66,48,50,94,87,100) ,利用快速排序,以第 一个关键字为分割元素,经过一次划分后结果为( ) 。 A.30,50,48,56,66,89,94,100,87 B. 50,30,48,56,66,89,94,87,100 C.48,30,50,56,66,89,94,87,100 D.50,30,48,66,56,89,94,87,100 28.设有一个 10 阶的对称矩阵 A,采用压缩存储的方式,将其下三角部分以行序为主存储到 一维数组 B 中(数组下标从 1 开始) ,则矩阵中元素 A8,5 在一维数组 B 中的下标是( A.33 B.32 C.85 D.41 29.线性表以( )方式存储,能进行折半查找。 A.关键字有序的链接 B.顺序 C.关键字有序的顺序 D.数组 C.多对多 D.每一个元素都有一个直接前驱和一个直接后继 30.在一个无向图中,所有顶点的度数之和等于边数的( )倍。 A.3 B.2.5 C.1.5 D.2 二、填空题 1. 数据的逻辑结构在计算机中的表示称为________结构。 2.栈和队列的操作特点分别是___ ____和 _____ ___。 3. 求两个 n 阶矩阵的乘积,算法的基本操作为________,时间复杂度为 ________。 4.结构中的数据元素存在多对多的关系称为_____ ___结构。 5.设有一个长度为 25 的顺序表,第 8 号元素到第 25 号元素依次存放的值为 8,9,10,11,?25, 某人想要在第 8 个元素前插入 1 个元素 7(也就是插入元素作为新表的第 8 个元素) ,他 的做法是从第 8 号元素开始,直到第 25 号元素依次向后移动 1 个位置,然后把 7 存放在 8 号位置,其结果是新表中第 25 号元素的值为_____ 。 6.根据数据元素间关系的不同特性,通常可分为集合、线性、 、 四类基本结 构。 7.在双向链表中,要在 p 所指的结后插入 q 所指的结点(设 q 所指的结点已赋值), 其中所用的一条语句(p->next)->prior=q; 的功能是使 P 所指结点的_______指向 q 。 8.要求在 n 个数据元素中找其中值最大的元素,设基本操作为元素间的比较。则比较的次数 和算法的时间复杂度分别为________和 ________ 。 9.设有一个带头结点的,头指针为 head 的单向链表,p 指向表中某一个结点,且有 p->next= =NULL,现要删除头结点,并使该单向链表构造成单向循环链表,通过 操作 head=head->next; ________。 10.在一个单向链表中 p 所指结点之后插入一个 s 所指向的结点时,应执行___ ____ _和 p->next=s;的操作。 11.从一个栈顶指针为 top 的链栈中删除一个结点时,用 d 保存被删结点的值,可执行 ________。(结点的指针域为 next,数据域为 data) 12.在二叉树的链式存储结构中,通常每个结点中设置三个域,它们是值域 、 。 13 循环链队列中,设 front 和 rear 分别为队头和队尾指针,(最多元素为 MaxSize,采用少用一 个元素的模式),判断循环链队列为满的条件为________ 。
3

) 。

14.一棵二叉树中顺序编号为 i 的结点,若它存在左、右孩子,则左、右孩子编号分别为 ________、________。 15.对稀疏矩阵进行压缩存储,可采用三元组表,一个 6 行 7 列的稀疏矩阵 A 相应的三元组 表共有 8 个元素,则矩阵 A 共有_______个零元素。 16.向一个栈顶指针为 h 的链栈中插入一个 s 所指结点时,可执行 s->next=h;和________。 17.一棵有 20 个结点的 4 度的树,其中 3 度结 1 个,2 度结 1 个,1 度结 2 个,则该树共有 _______个叶结点。 18.在一个链队中,设 f 和 r 分别为队头和队尾指针,则插入 s 所指结点的操作为________ 和 r=s; (结点的指针域为 next) 19.一棵有 18 个结点的二叉树,其 2 度结点数的个数为 8,则该树共有 _______个 1 度结点 20. 设有一棵深度为 4 的完全二叉树, 第四层上有 5 个结点, 该树共有_________个结点。 (根 所在结点为第 1 层) 21.如图 2 所示的二叉树,其先序遍历序列为_________。 2 b

1 a 5 e

3 c 7 g d 图2

4 d c 9

8 h d

6 f

22. 对稀疏矩阵进行压缩存储, 矩阵中每个非零元素对应的三元组包括该元素的_______、 ______ _和____ ___三项信息。 23. 在查找表中, 通过记录的某关键字能唯一地确定一个记录, 该关键字称为_________。 24.在对一组记录(55,39,97,22,16,73,65,47,88)进行直接插入排序时,当把第 7 个记录 65 插入到有序表时,为寻找插入位置需比较_________次。 三、综合题 1. (1)对给定权值 3,1 ,4,4,5,6,构造深度为 5 的哈夫曼树。(设根为第 1 层) (2) 求树的带权路径长度。 (3)链接存储上述哈夫曼树,结点中共有多少个个指针域为空,说明理由.

2. (1)以 2,3,4,7,8,9 作为叶结点的权,构造一棵哈夫曼树( 要求每个结点的左子树根结 点的权小于等于右子树根结点的权),给出相应权重值叶结点的哈夫曼编码。 (2) 一棵哈夫曼树有 n 个叶结点,它一共有多少个结点?简述理由?

4

3. (1) 如下的一棵树,给出先序遍历序列 (2) 把 1,2,3,4,5,6,7,8,9 填人,使它成为一棵二叉排序树 提示:设图中的树是二叉排序树,找出中序遍历序列与 1,2,…9 的对应关系 (3) 请在该树中再插入一个结点 3.5 作为叶结点,并使它仍然是一棵二叉排序树。 A1 A2 A3

A4 3 A7 A8

A5

A6

A9

图3

4.一组记录的关键字序列为(46,79,56,38,40,84) (1)利用快速排序的方法,给出以第一个记录为基准得到的一次划分结果(给出逐次交 换元素的过程,要求以升序排列) (2)对上述序列用堆排序的方法建立大根堆,要求以二叉树逐次描述建堆过程。

5.设查找表为(5,6,7,8,9,10,11,12,13,14) (1)画出对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点) (2) 给出二叉排序树的定义,针对上述折半查找所对应的判定树的构造过程,说明判定树 是否是二叉排序树(设树中没有相同结点)? (3) 为了查找元素 5.5,经过多少次元素间的比较才能确定不能查到?

6.设查找表为(50,60,75,85,96,98,105,110,120,130)
5

(1) 说出进行折半查找成功查找到元素 120 需要进行多少次元素间的比较? (2) 为了折半查找元素 95,经过多少次元素间的比较才能确定不能查到? (3)画出对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点)

四、程序填空题 1.以下函数为直接选择排序算法,对 a[1],a[2],?a[n]中的记录进行直接选择排序,完成 程序中的空格 typedef struct { int key; ?? }NODE; void selsort(NODE a[],int n) { int i,j,k; NODE temp; for(i=1;i<= ___(1)_____;i++) { k=i; for(j=i+1;j<= ___(2)_____;j++) if(a[j].key<a[k].key) __(3)______; if(i!=k) { temp=a[i]; ___(4)_____; ____(5)____; } } } 2.以下是用尾插法建立带头结点且有 n 个结点的单向链表的程序,结点中的数据域从 前向后依次为 1,2,3,……,n,完成程序中空格部分。 NODE *create(n) {NODE *head , *p, *q; int i; p=(NODE*)malloc(sizeof(NODE)); head= (1) ; (2) ;p?next=NULL; /*建立头结点*/ for(i=1; i<=n; i++) { p= (3) ; p?data=i; p?next=NULL; q?next= (4) ; (5) ;
6

} return(head); }

3 .设有一个头指针为 head 的不带头结点单向链表, 且 p、 是指向链表中结点类型的指针 q 变量,p 指向链表中某结点 a(设链表中没有结点的数据域与结点 a 的数据域相同), 写 出相关语句 (1).使该单向链表成为单向循环链表 (2) 删去 a 结点 q=p; x=p->data; while (q->next!=NULL)q=q->next; __(1)___ q=p; p=p->next; while(p->data!=x) { q=p; __(2)___ } __(3)___

4.以下程序是中序遍历二叉树的递归算法的程序,完成程序中空格部分(树结构中左、 右指针域分别为 left 和 right,数据域 data 为字符型,BT 指向根结点) 。 void Inorder (struct BTreeNode *BT) { if(BT!=NULL){ (1) ; (2) ; (3) ; } } 期末复习一答案 一、单项选择题 1.C 2.B 3.A 4.C 5.A 6.D 7.C 8.A 9.D 13. C 14.B 15.D 16.C 17.C 18. 19.B 20.C A 24.B 25.C 26.C 27.B 28.A 29.C 30.D 二、填空题 1.物理(存储) 2.后进先出、先进先出 3.乘法 O(n3) 4.图状 (网状)

10.D 11.C 12.C 21.A 22. A 23. B

7

5.8 6.树形 图状 7. 直接前驱的左指针 8.n-1,O(n) 、 9. p->next= head; 10.s->next=p->next; 11.d=top->data;top=top->next; 12.左指针 右指针 13.front= =(rear+1)% MaxSize 14.2i 2i+1 15.34 16.h=s; 17.13 18.r->next=s; 19.1 20.12 21.215347896 22.行下标、列下标、非零元素值 23.主关键字 24.3 三、综合应用题 1. (1)
23 41 14 51 8

9 7 4 3 5 4

3

4 5 3

8 9 6

6 5 4 3

1 2 1

图4

(2) WPL=3*4+1*4+4*3+6*2+4*2+5*2=58 (3) 共 11 个结点,22 个指针域,除根结点外,每个结点对应一个指针域.,共 10 个指针域非空,故 有 22-10=12 个空指针域,

8

2. (1)

33

15

18

7

8

9

9

4

5

2

3

图5 2:1110 3: 1111 4:110 7:00 8:01 9:10 (2)2n-1 个,因为非叶结点数比叶结点数少一个。 3. (1) A1 A2 A4 A7 A8 A5 A9 A3 A6 (2) (3) 7 4 8

2

5 3

9

1

6

3.5 图6 4. (1)初始序列
9

46,79,56,38,40,84 40,79,56,38,40,84 40,79,56,38,79,84 40,38,56,38,79,84 40,38,56,56,79,84 40,38,46,56,79,84 (2)
46 46

79

56

79

84

38

40

84

38

40 56

6
84

84

79

46

79

56

38

40 56

38

40 46

图6 5.(1)
9

6

12

5

7

10

13

8

11

14

图7 (2) 二叉排序树或者是一棵空树,或者是一棵具有下列性质的二叉排:若它的左子树 非空,则左子树的所有结点的值都小于它的根结点的值;若它的右子树非空,则右子 树的所有结点的值都大于(若允许结点有相同的值,则大于等于)它的根结点的值;

10

左,右子树也是一棵二叉排序树,按定义判定树是二叉排序树。 (3) 3 次 6. (1)3 次 (2)4 次 (3)
96

60

110 05 120

50

75

98

85

105

130

图8 四、程序填空题 1. (1)n-1 (2)n (3)k=j (4)a[i]=a[k] (5)a[k]=temp 2. (1)p (2)q=p (3)(NODE*)malloc(sizeof(NODE)) (4)p (5)q=p 3. (1) q->next=head; (2) p=p->next; (3) q->next=p->next; 4. (1)Inorder(BT->left) (2)printf(“%c”,BT->data) (3) Inorder(BT->right)
11

期末练习二 一、单项选择题 1 .结构中的元素之间存在一对多的关系是( ) 。 A.集合 B.线性结构 C.树形结构 D.图状结构 2.在 C 语言中,顺序存储长度为 3 的字符串,需要占用( )个字节。 A.4 B.3 C.6 D.12 3 .对不带头结点的单向链表,判断是否为空的条件是( ) (设头指针为 head) 。 A.head==NULL B.head->next= =NULL C.head->next= =head D.head =NULL 4.串函数 StrCat(a,b)的功能是进行串( ) 。 A.比较 B.复制 C.赋值 D.连接 5. 在一个不带头结点的单循环链表中,p、q 分别指向表中第一个结点和尾结点,现要删除 第一个结点,可用的语句是( ) 。 A.p=q->next; p=p->next; B.p->next=q ; p=p->next; C.p->next=q->next;q=p; D.p=p->next; q->next=p; 6.一棵有 n 个结点采用链式存储的二叉树中,共有( )个指针域为空。 A.n+1 B.n C.n-1 D.n-2 7.一个栈的进栈序列是 1,2,3,4,5,则栈的不可能输出序列是( ) (进栈出栈可以 交替进行) 。 A.12345 B.43512 C.45321 D.54321 8.设一棵哈夫曼树共有 n 个非叶结点,则该树有( )个叶结点。 A.n B.n+1 C.n-1 D.2n 9.一个队列的入队序列是 2,4,6,8,按该队列的输出序列使各元素依次入栈,该栈的可 能输出序列是 ( ) 。 A.8,6,4,2 B.6,2,4,8 C.8,4,2,6 D.8,2,4,6 10.从一个栈顶指针为 top 的链栈中删除一个结点时,用变量 x 保存被删结点的值,则执行 ( ) 。 A.x=top->data; top=top?next; B.x=top->data; C.top=top->next; x=top->data; D.top=top->next; x=data; 11.在一个链队中,假设 f 和 r 分别为队头和队尾指针,已生成一个结点 p,要为结点 p 赋 值 x,并入队的运算为( ) 。 A . p->data=x; p->next=NULL; f->next=p; f=p; B. p->data=x; p->next=NULL ;r->next=p;r=p; C. p->data=x; p->next=r;r=s; D. p->data=x; p->next=f;f=s; 12.一棵完全二叉树共有 5 层,且第 5 层上有六个结点,该树共有( )个结点。 A.30 B.20 C.21 D.23 13.设有一个 25 阶的对称矩阵 A,采用压缩存储的方式,将其下三角部分以行序为主序存储 到一维数组 B 中 (数组下标从 1 开始) 则矩阵中元素. 7,6 在一维数组 B 中的下标是 , a ( ) 。
12

A.34 B.14 C.26 D.27 14.在一个无向图中,所有顶点的度数之和等于边数的( )倍。 A.3 B.2.5 C.1.5 D.2 15.以下程序段的结果是 c 的值为( ) 。 char a[5]= “1236789”, int *p=a, int c=0; while(*p++)c++; A.8, B.7 C.10 D.12 16.已知如图 1 所示的一个图,若从顶点 V1 出发,按深度优先搜索法进行遍历,则可能得到 的一种顶点序列为( ) 。 A.V1V2V4V8V5V3V6V7 B.V1V2V4V5V8V3V6V7 C.V1V2V4V8V3V5V6V7 D.V1V3V6V7V2V4V5V8

V1

V2

V3

V4

V5

V6

V7

V8 图1 17.一棵有 23 个结点,采用链式存储的二叉树中,共有( )个指针域为空。 A.24 B.25 C.23 D.45 18.已知如图 2 所示的一个图,若从顶点 a 出发,按广度优先搜索法进行遍历,则可能得到 的一种顶点序列为( ) 。 A.abcedf B.abcefd C.aebcfd D.acfdeb a

b

e

c

d 图2

f

19.在一棵二叉树中,若编号为 i 的结点是其双亲结点的左孩子,则双亲结点的顺序编号为 ( ) 。

13

A.i/2 B.2i-1 C.2i+1 D.i/2 -1 20.对二叉排序树进行( )遍历,可以使遍历所得到的序列是有序序列。 A.按层次 B.后序 C.中序 D.前序 21.设一棵哈夫曼树共有 2n+1 个叶结点,则该树有( )个叶结点。 A.n-1 B.n C.n+1 D.2n 22.在有序表{2,4,7,14,34,43,47,64,75,80,90,97,120}中,用折半查找法查 找值 80 时,经( )次比较后查找成功。 A.4 B.2 C.3 D.5 23.已知如图 3 所示的一个图,若从顶点 a 出发,按深度优先搜索法进行遍历,则可能得到 的一种顶点序列为( ) 。 A.abecdf B.acfebd C.aebcfd D.aedbfc

a

e

c

b

d 图3

f

24.有一个长度为 9 的有序表,按折半查找对该表进行查找,在等概率情况下查找成功的平 均比较次数为( ) 。 A.25/10 B.25/9 C.20/9 D.17/9 25.已知如图 4 所示的一个图,若从顶点 B 出发,按广度优先法进行遍历,则可能得到的一 种顶点序列为( ) 。 A.BADEHCFG B.ADEHCGF C.BADECHFG D.BADEHCFG A

B

C

D V4

E

F

G V7

H V8 图4

14

26.排序算法中,从未排序序列中依次取出元素与已排序序列(初始为空)中的元素进行 比较(要求比较次数尽量少) ,然后将其放入已排序序列的正确位置的方法是( ) 。 A.冒泡 B.直接插入 C.折半插入 D.选择排序 27.一组记录的关键字序列为(46,38,56,40,79,84) ,利用快速排序,以第一个关键 字为分割元素,经过一次划分后结果为( ) 。 A.40,38,46,79,56,84 B.40,38,46,56,79,84 C.40,38,46,84,56,79 D.38,40,46,56,79,84 28.一组记录的关键字序列为(46,79,56,38,40,84) ,利用快速排序,以第一个关键 字为分割元素,经过一次划分后结果为( ) 。 A.40,38,46,79,56,84 B.40,38,46,56,79,84 C.40,38,46,84,56,79 D.38,40,46,56,79,84 29.在有序表{21,23,28,33,43,45,46,73,77,78,89,99,106}中,用折半查找 值 43 时,经( )次比较后查找成功。 A.6 B.3 C.8 D.4 30.排序方法中,从尚未排序序列中挑选元素,并将其依次放入已排序序列(初始为空)的 一端的方法,称为( )排序。 A.归并 B.插入 C.快速 D.选择 二、填空题 1. 本书中介绍的树形结构和_______ 属非线性结构。 2.在二叉树的链式存储结构中,通常每个结点中设置三个域,它们是_______、 、 右指针。 3.设有一个长度为 18 的顺序表,要在第 4 个元素之前插入 2 个元素(也就是插入元素作为 新表的第 5 个和第 4 个元素) ,则最少要移动元素的个数为( ) 。 4. 一棵二叉树中顺序编号为 i 的结点, 若它存在左、 右孩子, 则左、 右孩子编号分别为_____ _、___ _____。 5.在双向链表中,要删除 p 所指的结点,可以先用语句(p->prior)->next=p->next;然 再用语句________。 6.串的两种最基本的存储方式是_______ _和 __ ______。 7.在一个单向链表中 p 所指结点之后插入一个 s 所指向的结点时,应执行 s->next=p->next; 和 ___ ____的操作. 8.一棵有 2n-1 个结点的二叉树,其每一个非叶结点的度数都为 2,则该树共有_______个叶 结点。 9.一个栈和一个队列的输入序列都为 abcdefg,它们可能有相同的输出序列吗?_________。 (若没有则回答没有,若有则写出序列,进栈出栈可以交替进行) 。 10.对于一棵具有 n 个结点的二叉树,其相应的链式存储结构中共有________个指针域为空。 11.从一个栈顶指针为 top 的链栈中取栈顶元素,用 d 保存栈顶元素的值,可执行 ________。(结点的数据域为 data) 12.________遍历二叉排序树可得到一个有序序列。 13. 循环链队列中,设 front 和 rear 分别为队头和队尾指针,(最多元素为 MaxSize,),判断循环 链队列为空的条件是________为真 。 14.如图 5 所示的二叉树,其后序遍历序列为 。

15

a

b

c

d

e

f

g 图5

h i

15. 对稀疏矩阵进行压缩存储,可采用三元组表,设 a 是稀疏矩阵 A 相应的三元组表类型(结 构体类型)变量,a 中的一个成员项是三元组类型的结构体数组 data,按书中定义,若 a.data[0].i=2;a.data[0].j=3; a.data[0].v=16; 它提供的 A 数组的相关信息有_______ 16.如图 6 所示的二叉树,其先序遍历序列为_______ __。

a

b

c

d e f

g

图6 17.设有一棵深度为 5 的完全二叉树,该树共有 20 个结点,第五层上有 个叶结点。 (根所在结点为第 1 层) 18.图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是______的。(回答正确 或不正确) 19.中序遍历________树可得到一个有序序列。 20.二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩 子的值。这种说法是__________的。(回答正确或不正确) 21.如图 7 所示的二叉树,其后序遍历序列为_________。

16

1 a 5 e

2 b

3 c 7 g d

4 d c 9

8 h d 图7

6 f

22. 对记录序列排序是指按记录的某个关键字排序, 记录序列按_________排序结果是唯一的。 23 .给定一组权重值,构造哈夫曼树,哈夫曼树的高度一定是唯一的,这种说法是__________ 的。(回答正确或不正确) 24.按某关键字对记录序列排序,若 在排序前和排序后仍保持它们的前后 关系,则排序算法是稳定的,否则是不稳定的。

三、综合题 1. (1) 说明什么是顶点活动网(AOV 网)和拓扑序列 (2)设有向图 G 如下,写出 3 种拓扑序列, (3)在图 G 中增加一条边,使图 G 仅有一条拓扑序列

a d b

c

图8 2.设查找表为(16,15,20,53,64,7), (1)用冒泡法对该表进行排序(要求升序排列) ,写出每一趟的排序过程,通常对 n 个元 素进行冒泡排序要进行多少趟冒泡?第 j 趟要进行多少次元素间的比较? (2)在排序后的有序表的基础上,画出对其进行折半查找所对应的判定树.(要求以数据元 素作为树结点)

3.如下是一棵二叉排序树,A1,A2,…A9 代表 1,2,3,…9 中各个不同数字,
17

(1)给出对该树中序遍历的结果 (2) A3,A5,A7 的值各为多少? (3)请在该树中再插入一个结点 9 .5 作为叶结点,并使它仍然是一棵二叉排序树 A1 A2 A3

A4

A5

A6

A7

A8

A9

图9 4. (1) 设有查找表{5,14,2,6,18,7,4,16,3},依次取表中数据,构造一棵二叉排序树。 (2)说明如何由序列的二叉排序树得到相应序列的排序结果,对上述二叉排序给出中序 遍历的结果。

5. (1) 设有查找表{17,26,14,16,15,30,18,19,28},依次取表中数据构造一棵二叉 排序树. (2) 对上述二叉树给出后序遍历的结果 (3). 对上述二叉树给出中后序遍历的结果 (4)) 在上述二叉树中查找元素 15 共要进行多少次元素的比较?

6. (1)对给定权值 2,1,3,3,4,5,构造哈夫曼树。 (2)同样用上述权值构造另一棵哈夫曼树,使两棵哈夫曼树有不同的高度,并分别求 两棵树的带权路径长度。

四、程序填空题 1.以下函数是二叉排序树的查找算法,若二叉树为空,则返回根结点的指针,否则,返

18

回值是指向树结点的结构指针 p(查找成功 p 指向查到的树结点,不成功 p 指向为 NULL) 完成程序中的空格 typedef struct Bnode { int key; struct Bnode *left; struct Bnode *right; } Bnode; Bnode *BSearch(Bnode *bt, int k) /* bt用于接收二叉排序树的根结点的指针,k用以接收要查找的关键字*/ { Bnode *p; if(bt== ___(1)_____) return (bt); p=bt; while(p->key!= __(2)______) { if(k<p->key) ___(3)_____; else ___(4)_____; if(p==NULL) break; } return(___(5)_____); }
}

3 .设有一个头指针为 head 的不带头结点单向链表,p、q 是指向链表中结点类型的指针变 量,p 指向链表中结点 a, (设链表中没有结点的数据域与结点 a 的数据域相同),写出 相关语句 (1).使该单向链表成为单向循环链表 (2)插入结点 s,使它成为 a 结点的直接前驱 q=p; x=p->data; while (__(1)___ )q=q->next; q->next=head; q=p; p=p->next; while(p->data!=x) { q=p; __(2)___ } s->next=p; __(3)___

答案 一、单项选择题 1. 2. 3. 4. 5. 6. 7. C A A D D A B 8. 9. 10. B A A 14.D 15.B 16.A 17.A 18.B 19.A 20.C 21.C

11. 12. 13. B C D 22.A 23.D 24.B

19

25.C 26.C

27.B 28.B 29.B 30.D

二、填空题 1.图状结构 2.值域 左指针 3.15 4.2i 和 2i+1 5. (p->next)->prior=p->prior; 6.顺序存储 链式存储 7. p->next=s; 8.n 9.abcdefg 10.n+1 11.d=top->data; 12.中序 13.front= =rear 14.gdbeihfca 15.A 的第一个非零元素的下标为 2,3 ,元素为 16 16.abdefcg 17.5 18.正确 19.二叉排序 20.不正确 21.519876432 22.主关键字 23.不正确 24.关键字相等的记录 三、综合应用题 1. (1)原序列 16 15 15 16 15 16 15 16 15 7 7 15 (2)
16

20 20 20 7 16 16

53 53 7 20 20 20

64 7 53 53 53 53

7 64 64 64 64 64

n-1 趟 n-j 次

7

53

15

20

64

20

图 10

2. (1)原序列 16 15 15 15 15 7 (2)

15 16 16 16 7 15

20 20 20 7 16 16

53 53 7 20 20 20

64 7 53 53 53 53

7 64 64 64 64 64

n-1 趟 n-j 次

16

7

53

15

20

64

图 11 (3)平均查找长度=(1*1+2*2+3*3)/6=14/6

3. (1)

5

2

14

4

6

18

3

7

16

图 12 (2)中序遍历 中序 2,3,4,5,6,7,14,16,18 4. (1)
21

5

2

14

4

6

18

3

7

16

图 13 (2)中序遍历 中序 2,3,4,5,6,7,14,16,18

5. (1)

18

11

7

6

5

3

4

3

3

2 wpl1=45

1

(2)
18 11

7 5

3

4

6

2

1 图 15

3

3

wpl2=45

22

6. (1)答

18

11

7

6

5

3

4

3

3

2 wpl1=45 四、程序填空题 1. (1)NULL (2)k (3)p=p->left (4)p=p->right (5)p 2. (1)&a (2)d?next=NULL (3)p->data (4)p=p->next (5)p!=NULL 3. (1) q->next!=NULL (2) p=p->next; (3)q->next=s;

1

4. (1)Postorder(BT->left) (2)Postorder(BT->right) (3) printf(“%c”,BT->data)

23

期末练习三 一、单项选择题 1. 数据结构在计算机内存中的表示是指 ( ) 。 A.数据元素之间的关系 B.数据的存储结构 C.数据元素的类型 D.数据的逻辑结构 2. 在数据结构和算法中,与所使用的计算机有关的是 ( ) 。 A.数据元数间的抽象关系 B.数据的存储结构 C.算法的时间复杂度 D.数据的逻辑结构 3 . 结构中的元素之间存在多对多的关系是 ( ) 。 A.集合 B.线性结构 C.树形结构 D.图状结构 4 .对顺序表,以下叙述中正确的是 ( )。 A.用一组地址连续的存储单元依次存放线性表的数据元素 B.各个数据元素的首地址是连续的 C.数据元素不能随机访问 D.插入操作不需要移动元素 5. 设有一个长度为 20 的顺序表,要在第 5 个元素之前插入 1 个元素(也就是插入元素作为 新表的第 5 个元素) ,则移动元素个数为( ) 。 A.15 B.16 C. 5 D.4 6.设有一个长度为 25 的顺序表,要删除第 10 个元素(下标从 1 开始),需移动元素的个数为 ( ) 。 A.9 B.10 C.15 D.16 7.在一个尾指针为 rear 的不带头结点的单循环链表中,插入一个 s 所指的结点,并作为第一 个结点,可执行( ) 。 A.rear?next= s; s?next=rear?next B.rear?next=s?next; C.rear=s?next D.s?next=rear?next ; rear?next=s; 8. 设单向链表中,指针 p 指向结点 A,若要删除 A 的直接后继,则所需修改指针的操作为 ( )。

A.p->next=p->next->next; B.p=p->next; C.p=p->next->next;D.p->next=p ; 9.元素 a,b,c,d 按顺序依次进栈,则该栈的可能输出序列是( ) (进栈出栈可以交替 进行) 。 A.c,a,b,d B.d,b,c,a C.a,c,b,d D.d,c,a,b 10.元素 1,3,5,7 按顺序依次进栈,按该栈的可能输出序列依次入队列,该队列 的可能输出序列是( )(进栈出栈可以交替进行) 。 。 A.7,5,3,1 B.7,3,1,5 C.7,5,1,3 D.5,1,3,7 11. 从一个栈顶指针为 top 的链栈中取栈顶元素, 用变量 x 保存该元素的值, 则执行 ( ) 。 A.x=top->data; top=top?next; B.x=top->data; C.top=top->next; x=top->data; D.top=top->next; x=data; 12 .对一个栈顶指针为 top 的链栈进行进栈操作,设 P 为待进栈的结点,则执行( ) 。 A.p=top->next; top=top?next; B.p->next=top;

24

C.p->next=top;top=p; D.top=p; 13.设有一个对称矩阵 A,采用压缩存储的方式,将其下三角部分以行序为主序存储到一维 数组 B 中(数组下标从 1 开始) 数组共有 55 个元素,则该矩阵是( ,B )阶的对称矩 阵。 A.5 B.20 C.10 D.15 14.设有一个 18 阶的对称矩阵 A,采用压缩存储的方式,将其下三角部分以行序为主序存储 到一维数组 B 中(数组下标从 1 开始) ,则数组中第 33 号元素对应于矩阵中的元素是 ( ) 。 B.a7,6 A.a10,8 C.a9,2 D.a8,5

15.设有一个 18 阶的对称矩阵 A,采用压缩存储的方式,将其下三角部分以行序为主序存储 到一维数组 B 中(数组下标从 1 开始) ,则数组中第 53 号元素对应于矩阵中的元素是 ( ) 。 A.a8,5 , B.a10,8 C.a8,1, D.a7,6 16.设有一个 17 阶的对称矩阵 A,采用压缩存储的方式,将其下三角部分以行序为主序存储 到一维数组 B 中(数组下标从 1 开始) ,则矩阵中元素

a16

在一维数组 B 中的下标是

( ) 。 A.45, B.18 C.51 D.53 17 .以下程序段的结果是 c 的值为( ) 。 char * a[5]={“12378”, “1237”, “1236789”, “1237”, “123708”}; int i,c=0; for(i=0;i<5:i++) if(StrCmp(a[i], “1237”)==0)c++; A.2, B.5 C.0 D.1237 18.串函数 StrCmp( “ABCd”“ABCD” , )的值为( ) 。 A.0 B.-1 C.1 D.3 19.一棵采用链式存储的二叉树中,共有 n 个指针域被有效使用(即指针域为非空) 。该二叉 树有( )个结点。 A.n+1 B.n C.n-1 D.n-2 20.一棵采用链式存储的二叉树中有 n 个指针域为空,该二叉树共有( )个结点。 A.n+1 B.n C.n-1 D.n-2 21.在一棵二叉树中,若编号为 i 的结点是其双亲结点的右孩子,则双亲结点的顺序编号为 ( ) 。 A.i/2.0 B.i/2+1 C.2i+1 D.i/2 向下取整 22.设一棵哈夫曼树共有 n 个非叶结点,则该树有( )个结点。 A.2n B.2n+2 C.2n-1 D.2n+1 23.设一棵采用链式存储的二叉树,除叶结点外每个结点度数都为 2,该树结点中共有 2n 个 指针域为空。则该树有( )个叶结点。 A.2n B.2n+1 C.2n+2 D.n 24.一棵 结点数 31<n<40 的完全二叉树,最后一层有 4 个结点,则该树有( )个叶结点 A.18 B.17 C.36 D.35 25.已知如图 1 所示的一个图,若从顶点 a 出发,按广度优先搜索法进行遍历,则可能得到

25

的一种顶点序列为( ) 。 A.acedfb B.aecfdb

C.aecdfb

D.acebfd

a

e

c

b

d

f

图1 26.已知如图 1 所示的一个图,若从顶点 a 出发,按深度优先搜索法进行遍历,则可能得到 的一种顶点序列为( ) 。 A.abedfc B.acfebd C.aebcfd D.aedfbc 27.一组记录的关键字序列为(42,37,62,40,32,92) ,利用快速排序算法,以第一个关 键字为分割元素,算法经过一次划分后结果为( ) 。 A.32,37,40,42,62,92 B.37,32,40,42,62,92 C.32,40,37,42,62,92 D.32,37,42,40,62,92 28.一组记录的关键字序列为(46,20,30,79,56,38,40,84,90,110) ,利用快速排序,以 第一个关键字为分割元素,经过一次划分后结果为( ) 。 A.20,30,40,38,46,79,56,84,90,100 B.40,20,30,38,46,56,79,84,90,110 C.30,20,40,38,46,84,56,79,90,100 D.20,30 38,40,46,56,79,84,90,100 29.一组记录的关键字序列为(80,57,41,39,46,47) ,利用堆排序(堆顶元素是最小元素) 的方法建立的初始堆为( ) 。 A.39,46,41,57,80,47 B.39,47,46,80,41,57 C.41,39,46,47,57,80 D.39,80,46,47,41,57

a

b

e

c

d

f

图2 30.一组记录的关键字序列为(75,63,95,80,53,45,38,20) ,利用堆排序(堆顶元素 是最大元素)的方法建立的初始堆为( ) 。 A.95,80,75,63,53,45,38,20

26

B.95,63,75,80,53,45,38,20 c. 95, 80, 45, 63, 53, 75, 38, 20 D.95, 80, 75, 20, 53, 45, 38, 63 二、填空题 1.数据元素可以有一个或________组成。 2.数据元素之间的抽象关系称为________结构 。 3. 结构中的数据元素存在一对一的关系称为线性结构。而数据元素存在 _______ 的关系 称为图状结构。 4.要求在 n 个数据元素中找值最大的元素,其基本操作为________。算法的时间复杂 度为_______ 。 5.设有一个长度为 25 的顺序表,要删除前 3 个元素,则最少要移动元素的个数为( ) 。 6.设有一个长度为 25 的顺序表,第 8 号元素到第 25 号元素依次存放的值 为 8,9,10,11,?,25,某人想要删除第 8 个元素,他的做法是从第 25 号元素开始,直 到第 9 号元素依次向前移动 1 个位置,其结果新表中第 9 号元素的值为( ) 。 7.在双向链表中,要删除 p 所指的结点,其中所用的一条语句(p->prior)->next=p->next; 的功能是:使 P 所指结点的直接前驱的右指针指向________。 8.在双向链表中,要在 p 所指的结后插入 q 所指的结点(设 q 所指的结点已赋值),可以 先用语句 q->next=p->next; (p->next)->prior=q; 然后再用语句 q->prior=p;和语句________。 9.设有一个头指针为 head 的单向链表,p 指向链表中的某结点,若要使该链表成为单向 循环链表,可用语句 while(p->next!= NULL) p= p->next; 和________。 10.在一个单向链表中,要删除 p 所指结点的直接后继结点。则可以用操作 ________。 (用一条语句) 11.向一个栈顶指针为 top 的链栈中插入一个 p 所指结点时,某人用语句 top=p;p->next=top; 这样做的结果使 p 所指向的结点的指针域指向了 _______。 12.向一个栈顶指针为 top 的链栈中插入一个 p 所指结点时,可执行________操作。 ( 填两条语句, 结点的指针域为 next) 13.在一个链队中,设 front 和 rear 分别为队头和队尾指针,则 s 所指结点(数据域已赋值)的 入队操作为 s->next=NULL;.________和 rear=s; 14.在一个带头结点的链队中,设 front 和 rear 分别为队头和队尾指针,则删除一个结点 的操作为 p=front->next;_______=p->next;(结点 的指针域为 next, p 为辅助用指针) 15.设有 n 阶对称矩阵 A,用一维数组 s 压缩存储 A 的下三角元素,s 的下标从零开始, 元素 s[26]相应于 A 中的元素为_______。 16.设有 n 阶对称矩阵 A,用一维数组 s 压缩存储 A 的下三角元素,s 的下标从零开始,最 后一个元素的下标为 27,则 n=_______。 17.对稀疏矩阵进行压缩存储,可采用三元组表,设 a 是稀疏矩阵 A 相应的三元组表类型(结 构体类型)变量,a 中的一个成员项是三元组类型的结构体数组 data,按书中定义,若 data 的下标从零开始,最后一个元素下标为 10,又 data[10].i=8;a.data[10].j=5; a.data[10].v=36; 它 提供的 A 数组的相关信息有_______。 18. 一棵 3 度的树,其中 3 度结 1 个,2 度结 2 个,1 度结 2 个,则该树共有_______个 叶结点。 19.设有一棵有 78 个结点的完全二叉树,该树共有_________层。 (根所在结点为第 1 层) 20.一棵有 7 个叶结点的二叉树,其 1 度结点数的个数为 2,则该树共有
27

_______个结点 。 21.对于一棵具有________个结点的二叉树,其相应的链式存储结构中共有 n+1 个指针域空. 22.如图 2 所示的二叉树,其中序遍历序列为_________。 23.如图 2 所示的二叉树,其中序遍历序列为_________。

9 a 7 b 5 8 e 3 f 图3 2 b 4 g 6 c

1 a 5 e

3 c 7 g d 图4

4 d c 9

8 h d

6 f

24.二叉排序树或者是一棵空树,或者是一棵具有下列性质的二叉排:若它的左子树非空, 则左子树的所有结点的值都小于它的根结点的值;若它的右子树非空,则右子的所有结点的 值都大于(若允许结点有相同的值,则大于等于)它的根结点的值。这种说法是__________ 的。(回答正确或不正确)

三、综合题 1. (1)已知某二叉树的后序遍历序列是 debca,中序遍历序列是 dbeac,试画出该二叉树。 (2)若上述二叉树的各个结点的字符分别代表不同的整数(其中没有相等的) ,并恰好 使该树成为一棵二叉排序树,试给出 a、b、c、d、e 的大小关系。 (3)给出该树的前序遍历序列。

2. (1) 以 3,4,5,8,9,10 作为叶结点的权,构造一棵哈夫曼树。
28

(2) 给出相应权重值叶结点的哈夫曼编码。 (2) 一棵哈夫曼树有 2n-1 个结点,它是共有多少个权重值构造而成的?简述理由?

3. (1)利用筛选过程把序列{42,82,67,102,16,32,57,52}建成堆(小根堆) ,画出 相应的完全二叉树(不要求中间过程) 。 (2)写出对上述堆对应的完全二叉树进行中序遍历得到的序列。

4. (1)简述拓扑排序的步骤。 (2)说明有向图的拓扑序列不一定是唯一的原因。 (3)如何利用拓扑排序算法判定图是否存在回路。 (4)设有向图 G 如下,写出首先删除顶点 1 的 3 种拓扑序列。 1 2 3 4

5 4 3 4

6 5 图5

5.设查找表为(11,12,13,14,15,16,17,18,19,20,21) ,元素的下标从 0 开始。 (1)画出对上述查找表进行折半查找所对应的判定树(树中结点用数值表示) (2)说明成功查找到元素 15,19 各需要经过多少次比较? (3)说明查找不到元素 10,15.5 各需要经过多少次比较? (4)給出中序遍历判定树的序列。

6.设有序表为(21,22,23,24,25,26,27,28,29,30,31,32) ,元素的下标从 0 开始。 (1)说出有哪几个元素需要经过 4 次元素间的比较才能成功查到。 (2)画出对上述有序表进行折半查找所对应的判定树(树结点用数值表示) (3)设查找元素为 5,需要进行多少次元素间的比较才能确定不能查到。 (4)求在等概率条件下,成功查找的平均比较次数?

29

四、程序填空题 1 . 以下程序是折半插入排序的算法 设待排序的记录序列存放在 a[1],…a[n]中,以 a[0]作为辅助工作单元,以下程序是要把 a[i] 插入到已经有序的序列 a[1],…a[i-1]中。 void binsort (NODE a[ ],int n) { int x,i,j,s,k,m; for (i=2;i<=__(1)___;i++) { a[0]=a[i]; x= a[i].key; s=1; j=i-1; while (s<=j) { m=__(2)___ if( x<a[m].key) __(3)___ else __(4)___ } for ( k=i-1;k>=j+1;k- -) __(5)___=a[k]; a[j+1]=a[0]; }

}
2.以下程序是快速排序的算法 设待序的记录序列存放在 a[start],…a[end]中,按记录的关键字进行快速排序, 先进行 一次划分,再分别进行递归调用 void quicksort ( NODE a[ ], int start ,int end ) { int i,j; NODE mid ; if (start>=end ) return; i=start; j=end; mid=a[i]; while (i<j) { while(i<j && a[j].key>mid.key) j- -; if(i<j) { a[i]=a[j]; __(1)___; } while(i<j && a[i].key<=mid.key)
30

__(2)___; if(i<j) { __(3)___ __(4)___ } } a[i]=mid; quicksort (a,stat, i-1); quicksort __(5)___ } 3.以下函数为链栈的进栈操作,x 是要进栈的结点的数据域,top 为栈顶指针 struct node { ElemType data; struct node *next; }; struct node *top ; void Push(ElemType x) { struct node *p; p=(struct node*)malloc(___(1)_____); p->data=x; ___(2)_____; _____(3)___; } 4. 以下函数为链队列的入队操作, 为要入队的结点的数据域的值, x front、 rear 分别是 链 队列的队头、队尾指针 struct node { ElemType data; struct node *next; }; struct node *front,*rear; void InQueue(ElemType x) { struct node *p; p= (struct node*) ___(1)_____; p->data=x; p->next=NULL; ___(2)_____; rear= ___(3)_____; }

31

答案 一、单项选择题 1.B 2.B 3.D 4.A 5.B 14.D 15.B 16.C 17.A 25.C 26.A 27.A 28.B 二、填空题 1.多个数据项 2.逻辑 3.多对多 4.元素间的比较 O(n) 5.22 6.25 7.P 所指结点的直接后继 8.p->next=q; 9.p->next=head; 10.p->next=p->next->next; 11.p 本身 12.p->next=top; top=p; 13.rear->next=s; 14.front->next 15.a7,6 16.7

6.C 7.D 8.A 9.C 10.A 11.B 12.C 13.C 18.C 19.A 20.C 21.D 22.D 23.D 24.A 29.A 30.A

17.A 共有 11 个非零元素 ,a8,5 为 36 18.5 19.7 20.15 21.n 22.512389746 23.5387946 24.不正确 三、综合应用题 1. (1)

a c

b d
图6

e

32

(2)d<b<e<a<c (3)abdec

2.(1)

39 33

22 18

17 15 5

12 9

10 9

8

9

7

5

3

4

图7 (2) 3 0000 4 0001 5 001 10 01 8 10 9 11 (3)n 个,因为非叶结点数比叶结点数少一个,而权值个数=叶结点数 3. (1)
42 16

82

67

42

32

102

16

32

57

52

82

67

57

52
初始树 图8

102



33

(2)102,52,42,82,16,67,32,57 4 (1) 循环执行以下两步 选择一个度为 0 的顶点并输出 从网中删除此结点及所有出边 (2) 因为选择一个度为 0 的顶点时不一定是唯一的 (3) 由顶点活动网构造拓扑序列的过程中,输出结点后,余下的结点均有前驱 (4) 152364 152634 156234

5.
16

13

19

3
11 14 17 20 29 0 12 15 18 21

图9 (2) 4 次 2 次 (3)3 次 4 次 (4)11,12,13,14,15,16,17,18,19,20,21 6. (1) 5 (2)
26 16 23 22 13 21 01 24 31 4 22 11 25 15 28 18
30 20 32 2

29 19 27 17
31

0 0 0

0 2 (3) 3 0 (4) ASL=(1+2*2+3*4+5*4)/12=37/12 0

图 10

34

四、程序填空题 1. (1) n (2) (s+j)/2; (3) j=m-1; (4) s=m+1; (5) a[k+1] 2.(1) i++; (2) i ++; (3) a[j]=a[i]; (4) j--; (5) (a, i+1,end); 3. (1)sizeof (struct node) (2)p->next=top (3)top=p

4. (1)malloc(sizeof (struct node)) (2)rear->next=p (3)p

35


推荐相关:

数据结构(本)期末综合练习(2013年12月)

电​大​计​算​机​本​科​数​据​结​构​复​习​资​料数据结构期末综合练习 2013 年 12 月 期末综合练习一一、单项选择题 1...


数据结构(本)期末综合练习(2014年12月)

数据结构期末综合练习 2014 年 12 月 期末综合练习一一、单项选择题 1 .单向链表所具备的特点是( A.可以随机访问任一结点 C.插入删除不需要移动元素 )。 B....


数据结构(本)期末综合练习2010年12月(1)

电大数据结构电大数据结构隐藏>> 数据结构( 数据结构(本)期末综合练习 2010 年 12 月期末综合练习一一、单项选择题 1.数据的物理结构( )。 A.与数据的逻辑结构...


数据结构(本)期末综合练习(2015年11月)

数据结构(本)期末综合练习 2015 年 11 月综合练习一一、单项选择题 1.对稀疏矩阵进行压缩存储,可采用三元组表,一个 10 行 8 列的稀疏矩阵 A 共有 73 个...


数据结构(本)期末综合练习(2013年6月)

数据结构(本)期末综合练习(2013年6月)_理学_高等教育_教育专区。刚整理的数据...共 10 个指针域非空,故有 22-10=12 个空指针域, 3. (1)简述拓扑排序的...


数据结构(本)期末综合练习(2016年6月

数据结构(本)期末综合练习 2016 年 6 月 练习一一、单项选择题 1.下面关于...第4页 (根所在结点为第 1 层) 12. 广义表的( c, a , (a ,b) , d...


数据结构(本)期末综合练习(2013年6月)

数据结构(本)期末综合练习(2013年6月)_英语考试_外语学习_教育专区。数据结构(...(1+2*2+3*4+5*4)/12=37/12 图 10 11 6.(1) 9 6 12 5 7 10 ...


数据结构(本)期末综合练习(2013年6月)

数据结构(本)期末综合练习(2013年6月)_理学_高等教育_教育专区。数据结构(本)...故有 22-10=12 个空指针域, 5 3 4 5 3 8 9 6 6 5 4 3 3. (1...


数据结构期末综合练习(2009年6月)

数据结构(本)期末综合练习 2009 年 6 月为了帮助同学们进行期末复习,特拟定...12. 一棵二叉树总结点数为 11, 叶结点数为 5, 该树有___4___个双分支...


数据结构期末综合练习(2009年6月)

xyl0210贡献于2012-02-29 0.0分 (0人评价)暂无...数据结构( 数据结构(本)期末综合练习 2009 年 6 ...12 图5 (3)3 次 4. (1) 22 12 130 10 15...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com