内容发布更新时间 : 2025/1/6 16:57:49星期一 下面是文章的全部内容请认真阅读。

数据结构（本）期末综合练习

2015年11月

综合练习一

一、单项选择题

1.对稀疏矩阵进行压缩存储,可采用三元组表，一个10 行8列的稀疏矩阵A共有73 个零元素，其相应的三元组表共有( C )个元素。

A．8 B．80 C．7 D．10 2. 对稀疏矩阵进行压缩存储,可采用三元组表，一个10 行8列的稀疏矩阵A，其相应的 三元组表共有6个元素，矩阵A共有( C )个零元素。 A．8 B．72 C．74 D．10 3.字符串( A )是“abcd321ABCD”的子串。

A. “21AB” B. “abcD” C. “aBCD” D. “321a” 4. 程序段

char a[ ]=“abdcacdef”; char *p=a; int n=0;

while( *p!=‘\\0’){ n++; p++;} 结果中,n的值是（ D ）。 A. 6 B.8 C. 7 D.9 5.栈和队列的共同特点是（ A ）。

A．都是操作受限的线性结构 B．元素都可以随机进出

C．都是先进后出 D．都是先进先出 6. 10,6,2,1按顺序依次进栈，该队列的可能输出序列是（ A ）。

(进栈出栈可以交替进行）。

A．6,10,1,2 B．2,10,6,1 C．6,1,10,1 D．1,6,10,2

7. 在一个链队中，假设f和r分别为队头和队尾指针，p指向一个新结点,要为结点p 所指结点赋值x,并入队的运算为p->data=x; p->next=NULL;（ B ）。 A. f->next=p; f=p; B． r->next=p;r=p;

C． r=p; p->next=r; D． p->next=f;f=p;

8. 对一个栈顶指针为top的链栈进行出栈操作，用变量e保存栈顶元素的值 ，则执行 ( B ）。

A．e= top->next; top->data=e; B．e=top->data; top=top->next; C．top=top->next; e=top->data; D．top=top->next; e=data;

9. 数据结构中，与所使用的计算机无关的是数据的( A ) 结构。 A.逻辑 B.存储 C.逻辑与存储 D.物理 10. 算法的时间复杂度与( A )有关。

A. 算法本身 B. 所使用的计算机 C. 算法的程序设计 D. 数据结构 11．顺序表所具备的特点之一是（ A ）。

A．可以随机访问任一结点 B．不需要占用连续的存储空间 C．插入元素的操作不需要移动元素 D．删除元素的操作不需要移动元素 12．在一个单向链表中,在p所指结点之后插入一个s所指的结点时，可执行 s->next=p->next; 和（ D ）。

A．p= s; B． p->next=s->next; C．p=s->next D． p->next=s; 13. 数据元素是数据的基本单位，它（ C ）。 A．只能有一个数据项组成 B．至少有二个数据项组成

C．可以是一个数据项也可以由若干个数据项组成

D．至少有一个数据项为指针类型 14. 一种逻辑结构在存储时 （ C）。

A．只要存储数据元素间的关系 B．只能采用一种存储结构

C．可采用不同的存储结构 D．只要存储数据元素的值

15．设有头指针为head的非空的单向链表, 指针p指向其尾结点, 要使该单向链表成为单向循环链表,则可利用下述语句（C ）。

A．p =head; B．p=NULL; C．p->next =head; D．head=p; 16.单向链表所具备的特点是( C )。

A.可以随机访问任一结点 B.占用连续的存储空间 C.插入删除不需要移动元素 D.可以通过某结点的指针域访问其前驱结点 17. 在线性表的顺序结构中，以下说法正确的是（C ）。 A．逻辑上相邻的元素在物理位置上不一定相邻 B．数据元素是不能随机访问的

C．逻辑上相邻的元素在物理位置上也相邻

D．进行数据元素的插入、删除效率较高 18.数据结构在计算机内存中的表示是指 ( B ) 。

A．数据元素之间的关系 B．数据的存储结构 C．数据元素的类型 D．数据的逻辑结构 19.对链表, 以下叙述中正确的是（ A ）。

A．不能随机访问任一结点 B．结点占用的存储空间是连续的 C．插入删除元素的操作一定要要移动结点 D．可以通过下标对链表进行直接访问 20.下面关于线性表的叙述中,错误的是( B )。

A . 线性表采用顺序存储,必须占用一片连续的存储空间。

B. 线性表采用顺序存储,进行插入和删除操作,不需要进行数据元素间的移动。 C. 线性表采用链式存储，不必占用连续的存储空间。

D. 线性表采用链式存储，进行插入删除操作，不需要移动元素 21 .设有一个长度为35的顺序表，要在第5个元素之前插入1个元素（也就是插入元素 作为新表的第5个元素），则移动元素个数为（B ）。 A．30 B．31 C. 5 D．6 22 .设有一个长度为18的顺序表，要在第5个元素之前插入1个元素（也就是插入元素作为新表的第5个元素），则移动元素个数为（B ）。 A．15 B．14 C. 5 D．6

23．设有一个长度为40的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数为（ C ）。

A．11 B．10 C．30 D．31

24．设有一个长度为25的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数为（ C ）。

A．10 B．17 C．15 D．16

25．设有一个25阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素

a7,5在一维数组B中的下标是

（ C ）。

A．25 B．24 C．26 D．27

26．设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a10,8在一维数组B中的下标是

（ D ）。

A．62, B．63 C．51 D．53

27．线性表在存储后,如果相关操作中有要求:利用已知的指向某结点的指针或序号,访问 该结点的前驱结点，则采用（A ）的存储方式是不可行的。

A．单向链表 B．双向链表 C．单向循环链表 D．顺序表

28．在一个尾指针为rear的不带头结点的单循环链表中,插入一个s所指的结点,并作为第一个结点，可执行s?next=rear?next ;和（ D ）。

A． rear?next= s?next; B． rear =s?next;

C． rear=s; D． rear?next=s;

29．在一棵二叉树中，若编号为i的结点存在左孩子,i结点的左孩子的顺序编号为（ B ）。

A．i/2.0 B．2*i C．2*i+1 D．i+2

30．在一棵二叉树中，若编号为15的结点是其双亲结点的右孩子，则双亲结点的顺序编号为（D ）。

A．30 B．8 C．31 D．7 二、填空题

1. 广义表( ( b,a,c) ,c ,d , f , e , ( (i , j ) , k ) ) 的长度是___ 6_____。 2. 结构中的元素之间存在一对多的关系是___树形_____结构。

3. 数据结构中，数据元素之间的抽象关系称为____逻辑____结构。 4. 结构中的元素之间存在多对多的关系是 ___图状_____结构 。

5. 栈的操作特点是后进___先出_____ 。

6. 循环队列的最大存储空间为MaxSize ,若队头指针front，队尾指针rear，采用少用一个 存储空间以有效地判断栈空或栈满，队空的判定条件为___ rear==front为真_____ 。 7. 广义表(( b,a,c) ,c ,d , f , e ,( (i , j ) , k ) ) 的表头是____（b,a,c）____。 8. 广义表( ( b,a,c) ,c ,d , f , e , ( (i , j ) , k ) ) 的长度是____ 6____。

9. 设有一个长度为18的顺序表 , 第8号元素到第18号元素依次存放的值为8,9,…,18. 某人想要删除第8号元素，程序中他的做法是用语句for(i=18;i<=9;i--)a[i-1]=a[i]; 即从第18号元素开始, 直到第9号元素,每个元素依次向前(左)移动1个位置.事实上这

样做是错误的.其结果新表中第9号元素的值为___ 18 _____。 10．要求在n个数据元素中找值最大的元素，其基本操作为元素间的比较。算法的时间复杂 度为____ O(n)___ 。

11. 一棵二叉树,有1个2度结点,，2个1度结点，则该树共有 _ 5______个结点。