练习二
一、单项选择题
1栈和队列的共同特点是（ ）。
A. 元素都可以随机进出 B. 都是操作受限的线性结构 C. 都是先进后出 D. 都是先进先出 2．设有头指针为head的不带头结点的非空的单向循环链表, 指针p指向其尾结点, 要 删除第一个结点,则可利用下述语句 head=head->next;和（ ）。 A．p =head; B．p=NULL; C．p->next =head; D．head=p;
3.对一个栈顶指针为top的链栈进行入栈操作，通过指针变量 p生成入栈结点，则执 行：p=(struct node *)malloc(sizeof(struct node); p->data=a; 和（ ）。 A. p->nex=top; top=p; B. top->next=p; p=top;
C. top=top->next; p=top; D. p->next=top; p=top; 4. 以下说法正确的是( )。
A. 线性表的链式存储结构必须占用连续的存储空间 B. 一种逻辑结构可以有不同的存储结构
C．一种逻辑结构只能有唯一的存储结构 D．线性表的顺序存储结构不必占用连续的存储空间
5.设头指针为head的非空的单向链表, 指针p指向尾结点,则通过以下操作( ) 可使其成为单向循环链表。
A．p->next = NULL ; B．head = p;
C．p->next=head ; D．p=head;
6．把数据存储到计算机中，并具体体现( )称为物理结构。
A．数据的处理方法 B．数据的性质 C．数据的运算 D. 数据元素间的逻辑关系 7．一种逻辑结构（ ）。
A．只能有唯一的存储结构 B．可以有不同的存储结构 C．与存储该逻辑结构的计算机相关 D．是指某一种数据元素的性质 8．顺序表所具备的特点之一是（ ）。
A．可以随机访问任一结点 B．不需要占用连续的存储空间 C．插入元素的操作不需要移动元素 D．删除元素的操作不需要移动元素
9．把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（ ）。 A．存储结构 B．逻辑结构
C．数据元素的存储 D. 给数据元素分配存储空间
10．图状结构中数据元素的位置之间存在（ ）的关系。 A．一对一 B．一对多 C．多对多 D．每一个元素都有一个直接前驱和一个直接后继
11．图状结构中数据元素的位置之间存在（ ）的关系。 A．一对一 B．一对多
C．多对多 D．每一个元素都有一个且只有一个直接前驱和一个直接后继 12．元素20，14，16，18按顺序依次进栈，则该栈的不可能输出序列是（ ） （进栈出栈可以交替进行）。
A．18，16，14，20
第11页
B．20，14，16，18
C．18，16，20，14 D．14，20，18，16
13．一个单链表中,在p所指结点之后插入一个s所指的结点时，可执行: s->next=p->next;和（ ）。 A．s= p->next ; B．p->next=s->next; C．p=s->next ; D．p->next=s; 14．设有一个12阶的对称矩阵A(左上角第一个元素为a1,1)，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a5,4在一维数组B中的下标是（ ）。
A．14 B．12 C．13 D．11 15．元素12，14，16，18顺序依次进栈，则该栈的不可能输出序列是（ ）。 （进栈出栈可以交替进行）。
A．18，16，14，12 B．12，14，16，18 C．18，16，12，14 D．14，12，18，16
16．设有一个长度为22的顺序表，要删除第8个元素需移动元素的个数为（ ）。 A．25 B．14 C．15 D．23
17．设有一个30阶的对称矩阵A(第一个元素为a1,1)，采用压缩存储的方式，将其 下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元 素a9,2在一维数组B中的下标是（ ）。
A．41 B．32 C．18 D．38
18．在一棵二叉树中，若编号为5的结点存在右孩子，则右孩子的顺序编号为（ ）。 A．12 B．9 C．11 D．10
19．设有一个长度为32的顺序表，要删除第8个元素需移动元素的个数为（ ）。
A．15 B．22 C．14 D．24 20．一棵具有5层的完全二叉树，最后一层有4个结点，则该树总共有（ ）个结点。 A．14 B．15 C．19 D．18 21.在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（ ）。 A．2i B．2i-1 C．2i+1 D．2i+2 22 .如图1所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一
种顶点序列为（ ）。
A．abcdfge B．abcedfg C．acbfedg D．abcfgde a
b c
e
d f
第12页
g 图1
23．一棵具有16个结点的完全二叉树，共有（ ）层。(设根结点在第一层) A．7 B．5 C．6 D．4 24.字符串〝abcd321ABCD〞的子串是（ ）。 A. 〝21ABC〞 B.〝abcABCD〞 C. abcD D. 〝321a〞
25．如图2所示，若从顶点a出发，按图的深度优先搜索法进行遍历，则可能得 到的一种顶点序列为（ ）。
A．abecdfg B．acfebgd C．aebcfgd D．aedfcgb a b
e c g
d 图2
f
26.数组a经初始化char a[ ]=“English”; a[1]中存放的是（ ）。 A. 字符n B. 字符E C. 〝n〞 D. 〝E〞
27.字符串“DABcdabcd321ABC” 的子串是( )。 A. “cd32” B. “ABcD” C. “aBcd” D. “321a”
28．如图3所示，若从顶点a出发，按图的深度优先搜索法进行遍历，则可能得 到的一种顶点序列为（ ）。
A．abecdf B．acfebd C．aebcfd D．aedfcb
a
e c
d f
b
图3
第13页
29.如图4所示，若从顶点a出发，按广度优先搜索法进行遍历，则可 能得到的一种顶点序列为（ ）。
A．abcdfge B．abcdfeg C．acbfedg D．abcfgde
a
b
c
d f
g e
图4
30.下图5的拓扑序列是( )。
A．5 2 3 4 6 B．5 2 3 6 4 C．5 6 4 2 3 D. 2 3 4 5 6
2 3 4
56
图5
31 .设有一个长度为18的顺序表，要在第5个元素之前插入1个元素（也就是插入元素作 为新表的第5个元素），则移动元素个数为（ ）。 A．15 B．14 C. 5 D．6
32．设有一个长度为25的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数 为（ ）。
A．10 B．17 C．15 D．16
33．设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存 储到一维数组B中（数组下标从1开始），则矩阵中元素a10,8在一维数组B中的下标 是（ ）。
A．62, B．63 C．51 D．53 34．在一个尾指针为rear的不带头结点的单循环链表中,插入一个s所指的结点,并作为第 一个结点，可执行s?next=rear?next ;和（ ）。 A． rear?next= s?next; B． rear =s?next;
C． rear=s;
D． rear?next=s;
35．在一棵二叉树中，若编号为15的结点是其双亲结点的右孩子，则双亲结点的顺序编号
为（ ）。
第14页
A．30 B．8 C．31 D．7
二、填空题
1. 对稀疏矩阵进行压缩存储,可采用三元组表，一个有10行的稀疏矩阵A共有97个 零元素，其相应的三元组表共有3个元素。该矩阵A有 列。
2. 栈的特点之一是：元素进、出栈的次序是:先进_______。
3．在单向链表中，q指向p所指结点的直接后继结点 ，要删除q所指结点，可以用 操作______= q->next; 。
4．对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的三项信息 是____ ___。
5. 对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行下 标、列下标和____ ___三项信息。
6．在对10个记录的序列(9，35,19, 77 ,2, 10 ,53, 45,27,68)进行直接插入排序时，当把第 6个记录10 插入到有序表时，为寻找插入位置，元素间需比较_________次。 （按升序排序）
7. 队列的操作特点是后进________。
8. 字符串a1=〝beijing〞, a2 =〝bef〞 , a3= 〝beifang〞, a4=“befi〞最小的 是 ________。
9．n个元素进行冒泡法排序，通常需要进行____ ____趟冒泡。
10．10个元素进行冒泡法排序，,其中第5趟冒泡共需要进行____ ____次元素间的比较。 11． 中序遍历二叉排序树可得到一个________的序列。 12．________遍历一棵二叉排序树可得到一个有序序列。
13. 广义表( c , a , (a ,b) , d , e ,( (i ,j ) ,k ) )的长度是________ 。 14. 广义表( c , (a ,b,c) , ( d , e ,f ) , ( (i ,j ) ,k ) )的长度是________ .
15. 广义表的( c , a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是________ 。 16. 广义表的( c , (b,a ,b) , f , e ,( (i ,j ) ,k ) )深度是________ .
17. 循环队列在规定少用一个存储空间的情况下，队空的判定条件为________。
18. 序列4 , 2 , 5 , 3 ,8, 6,采用冒泡排序算法(升序),经一趟冒泡后, 结果序列是 ________。 19.c语言中,字符串“E”存储时占 个字节 。
20. 待排序的序列为8,3,4,1,2,5,9, 采用直接选择排序算法,当进行了两趟选择后,结果序列 为________。
21．一棵二叉树中有n个非叶结点，每一个非叶结点的度数都为2，则该树共有_______ 个叶结点。
22. 线性表用________方式存储可以随机访问 。 23．在对一组记录(55,39,97,22,16,73,65,47,88)进行直接插入排序时，当把第7个记录65 插 入到有序表时，为寻找插入位置需比较_________次。
24. 顺序表,,6，5，1, 2, 4, 3, 8，7经过一趟(1,1)归并后的结果序列为________。
25. 对一组记录（5，8，9，2，12，7，56，44，39）进行直接插入排序(由小到大排序) ，当把第6个记录7插入有序表，为寻找插入位置需比较________次。
26．设有一棵深度为6的完全二叉树，第6层上有3个结点，该树共有_______个结点。（根所在结点为第1层）
27．一棵有16个叶结点的哈夫曼树，则该树共有_______个结点。
28.20个元素进行冒泡法排序，通常第6趟冒泡要进行__ ____次元素间的比较。
29．对稀疏矩阵进行压缩存储,可采用三元组表，一个6行7列的稀疏矩阵A共有38个
第15页