数据结构（本）期末综合练习
2013年6月
期末综合练习一
1. 在数据结构和算法中，与所使用的计算机有关的是 （ ）。 A．数据元数间的抽象关系 B．数据的存储结构 C．算法的时间复杂度 D．数据的逻辑结构 2. 一种逻辑结构在存储时（ ）。
A．只要存储数据元素间的关系 B．只能采用一种存储结构 C．可采用不同的存储结构 D．只要存储数据元素的值 3 .对顺序表,以下叙述中正确的是 ( )。
A．用一组地址连续的存储单元依次存放线性表的数据元素 B．各个数据元素的首地址是连续的
C．数据元素不能随机访问 D．插入操作不需要移动元素 4 .对链表, 以下叙述中正确的是（ ）。
A．不能随机访问任一结点 B．结点占用的存储空间是连续的 C．插入删除元素的操作一定要要移动结点 D．可以通过下标对链表进行直接访问 5．设有一个长度为25的顺序表，要删除第10个元素(下标从1开始),需移动元素的个数为 （ ）。
A．9 B．10 C．15 D．16
6．线性表在存储后,如果相关操作是:要求已知第i个结点的位置访问该结点的前驱结点，则采用（ ）存储方式是不可行的。
A．单链表 B．双链表 C．单循环链表 D．顺序表 7. 设单向链表中,指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为( )。
A.p->next=p->next->next;
B.p=p->next;
C.p=p->next->next; D.p->next=p ; 8．栈和队列的共同特点是（ ）。
A．都是先进后出 B．元素都可以随机进出 C．只容许在端点处插入和删除元素 D．都是先进先出
9．元素1，3，5，7按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列 的可能输出序列是（ ）。（进栈出栈可以交替进行）。 A．7，5，3，1 B．7，3，1,5
C．7，5，1，3 D．5,1，3，7
10．元素2，4，6，8按顺序依次进栈，按该栈的的可能输出序列依次入队列，该队列的可能
输出序列是（ ）（进栈出栈可以交替进行）。 A．8，6，2，4 B．8，4，2，6
C．6，2，4，8 D．8，6，4，2
11 ．对一个栈顶指针为top的链栈进行进栈操作，设P为待进栈的结点，则执行（ ）。 A．p=top->next; top=top?next; B．p->next=top;
1
C．p->next=top;top=p; D．top=p;
12．在一个不带头结点的链队中，假设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
13．设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储
到一维数组B中（数组下标从1开始），则数组中第33号元素对应于矩阵中的元素是（ ）。(矩阵中的第1个元素是a1,1 ）
A．a7,6 B．a10,8 C．a9,2 D．a8,5
14．设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则数组中第38号元素对应于矩阵中的元素是（ ）。(矩阵中的第1个元素是a1,1 ）
A．a10,8 B．a7,6 C．a9,2 D．a8,5
15．设有一个17阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储
到一维数组B中（数组下标从1开始），则矩阵中元素
a10,6 在一维数组B中的下标是
（ ）。(矩阵中的第1个元素是a1,1 ）
A．45, B．18 C．51 D．53 16．在C语言中，分别存储 “S”和‘s’，各需要占用（ ）字节。 A．一个和两个 B．两个 C．一个 D．两个和一个 17．串函数StrCmp（“ABCd”，“ABCD”）的值为（ ）。
A．0 B．-1 C．1 D．3
18．一棵有n个结点，采用链式存储的二叉树中，共有（ ）个指针域被有效使用（即指针域为非空）。
A．n+1 B．n C．n-1 D．n-2
19．一棵采用链式存储的二叉树中有n个指针域为空,该二叉树共有（ ）个结点。 A．n+1 B．n C．n-1 D．n-2
20．在一棵二叉树中，若编号为i的结点存在双亲结点，则双亲结点的顺序编号为（ ）。 A．i/2.0 B．i/2向下取整 C．2i+1 D．i+2 21．设一棵哈夫曼树共有n个非叶结点，则该树有（ ）个结点。
A．2n B．2n+2 C．2n-1 D．2n+1 22．设一棵哈夫曼树共有2n+1个结点，则该树有（ ）个非叶结点。 A．n B．n+1 C．n-1 D．2n
23．一棵 结点数31 24．一棵完全二叉树共有4层，且第4层上有2个结点，该树共有（ ）个非叶子结点 (根为第一层)。 A．5 B．4 C．3 D．9 25．已知如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到 的一种顶点序列为（ ）。 A．abedfc B．acfebd C．aebcfd D．aedfbc 2 a b e c d 图1 f 26．如图2所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一 种顶点序列为（ ）。 A．abedfc B．acfebd C．aebcdf D．aebcfd a b e c d f 图2 27．一组记录的关键字序列为（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 28．一组记录的关键字序列为（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 29．一组记录的关键字序列为（75，63，95，80，53，45，38，20），利用堆排序（堆顶元素是最大元素）的方法建立的初始堆为（ ）。 A．95，80，75，63，53，45，38，20 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 30．线性表以（ ）方式存储，能进行折半查找。 A．关键字有序的链接 B．顺序 C．关键字有序的顺序 D．数组 3 二、填空题 1．数据元素之间的抽象关系称为__逻辑__结构 。 2. 数据的逻辑结构在计算机中的表示称为__物理（存储）__结构。 3．要求在n个数据元素中找值最大的元素，其基本操作为_元素间的比较_。算法的时间复杂 度为_ O(n)__ 。 4. 求两个n阶矩阵的乘积，算法的基本操作为_乘法__，时间复杂度为 _ O(n3)__。 5．设有一个长度为25的顺序表,第8号元素到第25号元素依次存放的值 为 8,9,10,11,?,25，某人想要删除第8个元素，他的做法是从第25号元素开始,直 到第9号元素依次向前移动1个位置,其结果新表中第9号元素的值为（25 ）。 6． 设有一个长度为25的顺序表,第8号元素到第25号元素依次存放的值为8,9,10,11,?25, 某人想要在第8个元素前插入1个元素7（也就是插入元素作为新表的第8个元素），他 的做法是从第8号元素开始,直到第25号元素依次向后移动1个位置,然后把7存放在 8号位置，其结果是新表中第25号元素的值为（ 8 ）。 7．在双向链表中，要在p所指的结后插入q所指的结点(设q所指的结点已赋值)，可以 先用语句q->next=p->next; （p->next）->prior=q； 然后再用语句q->prior=p;和语句__ p->next=q；__。 8．在双向链表中，要在p所指的结后插入q所指的结点(设q所指的结点已赋值)， 其中所用的一条语句（p->next）->prior=q； 的功能是使P所指结点的__直接前驱的左指针_____指向q 。 9．在一个单向链表中，要删除p所指结点的直接后继结点。则可以用操作 _ p->next=p->next->next;_______。（用一条语句） 10．设有一个带头结点的，头指针为head的单向链表，p指向表中某一个结点，且有 p->next= =NULL,现要删除头结点，并使该单向链表构造成单向循环链表，通过 操作head=head->next; _ p->next= head;_______。 11．向一个栈顶指针为top的链栈中插入一个p所指结点时，可执行__ p->next=top; top=p；操作。( 填两条语句, 结点的指针域为next) 12．从一个栈顶指针为top的链栈中删除一个结点时，用d保存被删结点的值，可执行 _ d=top->data;top=top->next;_______。(结点的指针域为next,数据域为data) 13．在一个带头结点的链队中，设front和rear分别为队头和队尾指针，则删除一个结点 的操作为 p=front->next;_ front->next______=p->next;(结点的指针域为next, p为辅助用指针) 14.循环链队列中，设front和rear分别为队头和队尾指针，(最多元素为MaxSize,采用少用一 个元素的模式),判断循环链队列为满的条件为_ front= =(rear+1)% MaxSize_______ 。 15．设有n阶对称矩阵A，用一维数组s压缩存储A的下三角元素，s的下标从零开始，最 后一个元素的下标为27，则n=__ 7___。(矩阵中的第1个元素是a1,1 ） 16．对稀疏矩阵进行压缩存储,可采用三元组表，一个6行7列的稀疏矩阵A相应的三元组 表共有8个元素,则矩阵A共有__ 34__个零元素。 17. 一棵3度的树，其中3度结1个，2度结2个，1度结2个，则该树共有_ 5___个 叶结点。 18.一棵有8个权重值构造的哈夫曼数，共有 15 个结点。 19．一棵有7个叶结点的二叉树，其1度结点数的个数为2，则该树共有 15___个结点 20．一棵有18个结点的二叉树，其2度结点数的个数为8，则该树共有___ 1__个1度结点 21．如图3所示的二叉树，其中序遍历序列为__ 512389746_______。 4 21578图3 22．如图4所示的二叉树，其先序遍历序列为__ 215347896_______。 21578 图4 9 3469 346 23．二叉排序树或者是一棵空树，或者是一棵具有下列性质的二叉排：若它的左子树非空，则左子树的所有结点的值都小于它的根结点的值；若它的右子树非空，则右子的所有结点的值都大于（若允许结点有相同的值，则大于等于）它的根结点的值。这种说法是_不正确_______的。(回答正确或不正确) 24．在查找表中，通过记录的某关键字能唯一地确定一个记录，该关键字称为__主关键字___。 三、综合题 1． (1) 以3，4，5，8，9，10作为叶结点的权，构造一棵哈夫曼树。 (2) 给出相应权重值叶结点的哈夫曼编码。 (3) 一棵哈夫曼树有2n-1个结点，它是共有多少个权重值构造而成的？简述理由？ 1．(1) 39 2217 12108 9 7 5 3 4 5