数据结构期末练习题

- .

-

.可修编- 1. 数据的不可分割的基本单位是 ( A )。

A．元素 B．结点 C．数据类型 D．数据项

2. 计算机处理数据的最小单位是（D ）。

A．元素 B．结点 C．数据类型 D．数据项

3. 算法是指 ( C )。

A．计算方法 B．排序方法

C．解决问题的有限运算步骤 D．查找方法

4. 顺序存储结构中数据元素之间的逻辑关系是由（ C ）表示的

A 线性结构 B 非线性结构 C 存储位置 D 指针

5. 单循环链表的主要优点是（ B ）。

A 不再需要头指针了 B 从表中任一结点出发都能扫描到整个链表；

C 已知某个结点的位置后，能够容易找到它的直接前趋；

D 在进行插入、删除操作时，能更好地保证链表不断开。

6. 一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是( C )。

A 54321 B 45321 C 43512 D 12345

7. 常对数组进行的两种基本操作是( B )

A．建立和删除 B． 索引和修改 C．插入和修改 D．插入和索引

8. 算法分析的两个主要方面是（A ）。

A空间性能和时间性能 B正确性和简明性 C 可读性和文档性 D 数据复杂性和程序复杂性 此题的解决步骤是如果出现一个三元素顺序是a、b、c，且a>c>b,则为不可能序列 - .

贵州大学理学院数学系信息与计算科学专业

《数据结构》期末考试试题及答案

(2003-2004学年第2学期)

一、 单项选择题

1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（ ）。

(A)、正确性 (B). 可行性 (C). 健壮性 (D). 输入性

2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（ ）。

for(i=n-1；i>=0；i--)

for(j=0；j

(A)、n2 (B). O(nlgn) (C). O(n) (D). O(n2)

3．折半查找法适用于（ ）。

（A）、有序顺序表 （B）、有序单链表

（C）、有序顺序表和有序单链表都可以 （D）、无限制

4．顺序存储结构的优势是（ ）。

（A）、利于插入操作 （B）、利于删除操作

（C）、利于顺序访问 （D）、利于随机访问

5．深度为k的完全二叉树，其叶子结点必在第（ ）层上。

（A）、k-1 （B）、k （C）、k-1和k （D）、1至k

6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（ ）

（A）、11 （B）、13 （C）、48 （D）、37

7．图的Depth-First Search(DFS)遍历思想实际上是二叉树（ ）遍历方法的推广。

（A）、先序 （B）、中序 （C）、后序 （D）、层序

8．在下列链队列Q中，元素a出队的操作序列为（ ）

Q

（A）、p=Q.front->next; p->next= Q.front->next;

（B）、p=Q.front->next; Q.front->next=p->next;

（C）、p=Q.rear->next; p->next= Q.rear->next;

1.

数据的不可分割的基本单位是 ( A )。

A．元素 B．结点 C．数据类型 D．数据项

2. 计算机处理数据的最小单位是（ D ）。

A．元素 B．结点 C．数据类型 D．数据项

3. 算法是指 ( C )。

A．计算方法 B．排序方法

C．解决问题的有限运算步骤 D．查找方法

4. 顺序存储结构中数据元素之间的逻辑关系是由（ C ）表示的

A 线性结构 B 非线性结构 C 存储位置 D 指针

5. 单循环链表的主要优点是（ B ）。

A 不再需要头指针了 B 从表中任一结点出发都能扫描到整个链表；

C 已知某个结点的位置后，能够容易找到它的直接前趋；

D 在进行插入、删除操作时，能更好地保证链表不断开。

6. 一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是( C )。

A 54321 B 45321 C 43512 D 12345

7. 常对数组进行的两种基本操作是( B )

A．建立和删除 B． 索引和修改 C．插入和修改 D．插入和索引

8. 算法分析的两个主要方面是（ A ）。

A空间性能和时间性能 B正确性和简明性 C 可读性和文档性 D 数据复杂性和程序复杂性

9. 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区， 该缓冲区应该是一个（ B ）结构。 //需满足先进先出原则

A 栈 B 队列 C 数组 D 线性表

10. 二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9，则存放A至少需要（ D ）个字节。

A 90 B 180 C 240 D 540

11. 讨论树、森林和二叉树的关系，目的是为了（ B ）。 此题的解决步骤是如果出现一个三元素顺序是a、b、c，且a>c>b,则为不可能序列 A 借助二叉树上的运算方法去实现对树的一些运算

第1页 共8页 第1章 1. 数据结构被形式地定义为（K，R），其中K是（ B ）的有限集合，R是K上关系的有限集合。 算法 数据元素 数据操作 逻辑结构 2. 数据结构被形式地定义为（K，R），其中K是数据元素的有限集合，R是K上（ D ）的有限集合 操作 映象 存储 关系 3. 数据结构研究的内容是( D )。 数据的逻辑结构 数据的存储结构 建立在相应逻辑结构和存储结构上的算法 包括以上三个方面 4. 数据结构是研究数据的（ C）以及它们之间的相互关系。 理想结构，物理结构 理想结构，抽象结构 物理结构，逻辑结构 抽象结构，逻辑结构 5. 数据结构是一门研究非数值计算的程序设计问题中计算机的 （ A ）以及它们之间的关系和运算等的学科。 数据元素 计算方法 逻辑存储 数据映像 6. 数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（ B ）和运算等的学科。 结构 关系 运算 算法 7. 算法分析的目的是（ C ）。 找出数据结构的合理性 研究算法中的输入和输出的关系 分析算法的效率以求改进 分析算法的易懂性和文档性 8. 算法分析的两个主要方面是（ A ）。 空间复杂性和时间复杂性 正确性和简明性 可读性和文档性 数据复杂性和程序复杂性 9. 算法分析的主要任务是（ C ）。 探讨算法的正确性和可读性 探讨数据组织方式的合理性 为给定问题寻找一种性能良好的解决方案 研究数据之间的逻辑关系 10. 计算机算法指的是（ C）。 计算方法 排序方法 解决问题的有限运算序列 调度方法 11. 一个正确的算法应该具有5个特性，除输入、输出特性外，另外3个特性是（ A ）。 确定性、可行性、有穷性 易读性、确定性、有效性 有穷性、稳定性、确定性 可行性、易读性、有穷性 12. 在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（ B ）。 逻辑结构 顺序存储结构 链表存储结构 以上都不对 13. 数据结构中，在逻辑上可以把数据结构分成：（ C ）。 动态结构和静态结构 紧凑结构和非紧凑结构 线性结构和非线性结构 内部结构和外部结构 14. 以下关于数据的逻辑结构的叙述中正确的是（ A )。 数据的逻辑结构是数据间关系的描述 数据的逻辑结构反映了数据在计算机中的存储方式 数据的逻辑结构分为顺序结构和链式结构 数据的逻辑结构分为静态结构和动态结构 15. 链式存储的存储结构所占存储空间（ A ）。 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 只有一部分，存放结点值 只有一部分，存储表示结点间关系的指针 分两部分，一部分存放结点值，另一部分存放结点所占单元数 16. 组成数据的基本单位是（C ）。 数据项 数据类型 数据元素 数据变量 第2章 1. 以下属于顺序存储结构优点的是( A )。 存储密度大 插入运算方便 删除运算方便 可方便地用于各种逻辑结构的存储表示 2. 下面关于线性表的叙述中，错误的是( B )。 线性表采用顺序存储，必须占用一片连续的存储单元。 线性表采用顺序存储，便于插入和删除操作。 线性表采用链接存储，不必占用一片连续的存储单元。 线性表采用链接存储，便于插入和删除操作。 3. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A ）存储方式最节省时间。 顺序表 双链表 带头结点的双循环链表 单循环链表 4. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 单链表 仅有头指针的单循环链表 双链表 仅有尾指针的单循环链表 5. 在一个长度为n的顺序表中删除第i个元素时，需向前移动（A ）个元素 n-i n-i+l n-i-1 i 6. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（ C）个元素结点 n/2 n (n+1)/2 (n-1)/2 7. 线性表的顺序存储结构是一种（ A ）的存储结构。随机存取 顺序存取 索引存取 散列存取 第2页 共8页 8. 一个顺序表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( B) 110 108 100 120 9. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（C ）个元素。 64 63 63.5 65 10. 线性表采用链式存储结构时，其地址（ D）。 必须是连续的 部分地址必须是连续的 一定是不连续的 连续与否均可以 11. 下列有关线性表的叙述中，正确的是（A ） 线性表中的元素之间是线性关系 线性表中至少有一个元素 线性表中任何一个元素有且仅有一个直接前趋 线性表中任何一个元素有且仅有一个直接后继 12. 线性表是具有n个（C ）的有限序列（n≠0) 表元素 字符 数据元素 数据项 第3章 1. 已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（C）5，4，3，2，1，6 2，3，5，6，1，4 3，2，5，4，1，6 1，4，6，5，2，3 2. 设有一个栈，元素的进栈次序为A、B、C、D、E，下列是不可能的出栈序列（ C） A, B, C, D, E B, C, D, E, A E, A, B, C, D E, D, C, B, A 3. 在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（ C） top不变 top=0 top->top++ 4. 向一个栈顶指针为hs的链栈中插入一个s结点(地址变量s)时，应执行( B) hs->next=s; s->next=hs;hs=s; s->next=hs>-next;hs->next=s; s->next=hs; hs=hs->next; 5. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为( D) (front+l)％n==rear (rear-l)％n==front rear==front (rear+l)％n==front 6. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为（ C） rear-1==front front+l==rear rear==front (rear+l)％n==front 7. 在一个链队列中，假定front和rear分别为队首和队尾指针(这里-表示箭头)，则删除一个结点的操作为（A ） front=front-next rear=rear-next rear=front-next front=rear-next 8. 某堆栈的输入序列为1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素为( C) i n-i n-i+1 哪个元素无所谓 9. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( D )。仅修改队头指针 仅修改队尾指针 队头、队尾指针都要修改 队头、队尾指针都可能要修改 10. 一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（ C）。edcba decba dceab abcde 11. 栈结构通常采用的两种存储结构是（A )。 顺序存储和链表存储 散列方式和索引方式 单链表和双链表存储 线性存储结构和非线性存储结构 12. 判定一个栈ST(最多元素为m0)为空的条件是（B ）。 ST->top!=0 ST->top==0 ST->top!=m0 ST->top==m0 13. 判定一个栈ST(最多元素为m0)为栈满的条件是（ D）。 ST->top!=0 ST-top==0 ST-top!=m0 ST-top==m0 14. 4个元素a1，a2，a3和a4依次通过一个栈，则不可能的出栈序是（ C ） a4，a3，a2，a1 a3，a2，a4，a1 a3，a1，a4，a2 a3，a4，a2，a1 15. 一个队列的入列序列是1,2,3,4,则队列的输出序列是（B ）。 4,3,2,1 1,2,3,4 1,4,3,2 3,2,4,1 16. 循环队列用数组A[0,…,m-1]存放其元素值,已知其头尾指针分别是front和rear则当前队列中的元素个数是（A ） (rear-front+m)%m rear-front+1 rear-front-1 rear-front 17. 数组Q[0,…,m-1]存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的下一个位置和当前队列中元素的个数，队列第一个元素的实际位置是（ D ） rear－qulen rear－qulen＋1 m－qulen (rear－qulen＋m)%m 18. 栈和队列的共同点是（C ） 都是先进后出 都是先进先出 只允许在端点处插入和删除元素 没有共同点 19. 表达式a*(b+c)-d的后缀表达式是（ B）。 abcd*+- abc+*d- abc*+d- -+*abcd 第3页 共8页 第6章 1. 树最适合用来表示（C ）。 有序数据元素 无序数据元素 元素之间具有分支层次关系的数据 元素之间无联系的数据 2. 如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ C ） 栈 队列 树 图 3. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ D ） 5 6 7 8 4. 已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（ D ） 0 1 48 49 5. 用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为（C ） n-1 n n+l 2n 6. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ C ） 250 251 501 500 7. 有n个叶子的哈夫曼树的结点总数为（ D） 不确定 2n 2n+1 2n-1 8. 一棵二叉树高h，所有结点的度或为0或为2，则这棵二叉树最少有(B )结点。2h 2h-1 2h+1 h+1 9. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ C ）的二叉树 空或只有一个结点 任一结点无左子树 高度等于其结点数 任一结点无右子树 10. 引入二叉线索树的目的是（ A ） 加快查找结点的前驱或后继的速度 为了能在二叉树中方便的进行插入与删除 为了能方便的找到双亲 使二叉树的遍历结果唯一 11. n个结点的线索二叉树上含有的线索数为（ C ） 2n n－l n＋l n 12. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为( C ) X的双亲 X的右子树中最左的结点 X的左子树中最右结点 X的左子树中最左结点 13. 在线索化二叉树中, 结点结构增加了两个指针域，以存放（ B ）的信息。 后继结点 前驱和后继结点 左右孩子结点 双亲结点 14. 二叉树按某种顺序线索化后,任一结点均有指向其前趋和后继的线索,这种说法（B）正确 错误 不同情况下答案不确定 有道理 15. 按照二叉树的定义,具有3个结点的二叉树有（ C）种。 3 4 5 6 16. 在一非空二叉树的中序遍历序列中,根结点的右边（ A ） 只有右子树上的所有结点 只有右子树上的部分结点 只有左子树上的部分结点 只有左子树上的所有结点 17. 二叉树的特点包括（D ）。 可为空树 每个结点的度不超过2 子树有左、右之分 以上都包括 18. 在下述结论中，正确的是（ A）。 只有一个结点的二叉树的度为0 二叉树的度为2 二叉树的左右子树可任意交换 树都分左右子树 19. 树的存储方式有（ D ）。 双亲表示法 孩子表示法 孩子兄弟表示法 以上都包括 20. 在一棵树的静态双亲表示中，每个存储结点包含( B )个域。 1 2 3 4 21. 若下面几个符号串编码集合中，不属于前缀编码的是（ B ）。 {0,10,110,1111} {11,10,001,101,0001} {00,010,0110,1000} {b,c,aa,ac,aba,abb,abc} 22. 若由森林转化得到的二叉树是非空的二叉树，则二叉树的形状是（ C ）。 根结点无右子树的二叉树 根结点无左子树的二叉树 根结点可能有左二叉树和右二叉树 各结点只有一个孩子的二叉树 23. 设森林F对应的二叉树B有m个结点，B的根的右子树有n个结点，则F中第一棵树的结点个数是（ A ） m-n m-n-1 n+1 条件不足，无法确定 24. 设森林F中有三棵树，第一到第三棵树的结点个数分别为M1、M2和M3。对应F的二叉树根结点的右子树上的结点个数是（ D ） M1 M1+M2 M3 M2+M3 25. 实现任意二叉树的后序遍历的非递归算法而不使用栈结构,最佳方案是二叉树采用（ C）存储结构。 二叉链表 广义表存储结构 三叉链表 顺序存储结构 26. 有关树的叙述中，正确的是（ C ）。 二叉树中每个结点都有两个子结点 树都分左右子树 树可以有多个直接后继 森林必须由3棵以上的树组成 27. 有关赫夫曼树的叙述中正确的是：哈夫曼树（ C ）。 由一组权值构造时一定是唯一的 是权值之和最小的二叉树 是带权路径长度最小的二叉树 是路径长度之和最小的树 28. 下面关于哈夫曼树的说法中，哈夫曼树（ D）是不正确的。 由一组权值构造时一般不是唯一的 具有