最新国家开放大学电大《数据结构》期末题库及答案
考试说明：本人针对该科精心汇总了历年题库及答案，形成一个完整的题库，并且每年都在更新。该题库对考生的复习、作业和考试起着非常重要的作用，会给您节省大量的时间。做考题时，利用本文档中的查工具，把考题中的关键字输到查工具的查内容框内，就可迅速查到该题答案。本文库还有其他网核及教学考一体化答案，敬请查看。
《数据结构》题库及答案一
一、 单项选择题
1. 给定有n个元素的向量，建立一个有序单链表的时间复杂度是（ C ）。
  A. O(1)     B. O(n)
  C. O(n2)   D. O(nlog2n)
2. 带表头的双向循环链表的空表满足（ B ）。
  A. first＝NULL;         B. first->rLink==first
  C. first->lLink==NULL  二叉树定义 D. first->rLink==NULL
3. 栈的插入和删除操作在( A )进行。
  A. 栈顶       B. 栈底
C. 任意位置   D. 指定位置
4. 在一个顺序存储的循环队列中，队头指针指向队头元素的( A )位置。
  A. 前一个   B. 后一个
C. 当前    D. 后面
5. 假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为( D )。
  A. front+1 == rear   B. rear+1 == front
  C. front == 0       D. front == rear
6. 设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行( A )操作。
  A. x=top->data; top=top->link; B. top=top->link; x=top->data;
  C. x=top; top=top->link;       D. x=top->data;
7. 为增加内存空间的利用率和减少溢出的可能性, 由两个栈共享一块连续的内存空间时, 应将两栈的( D )分别设在这块内存空间的两端。
  A. 长度     B. 深度
C. 栈顶     D. 栈底
8. 在系统实现递归调用时需利用递归工作记录保存（ C ），当递归调用程序执行结束时通过它将控制转到上层调用程序。
  A. 调用地址  B. 递归入口
C. 返回地址  D. 递归出口
9. 如果一个递归函数过程中只有一个递归语句，而且它是过程体的最后语句，则这种递归属于（ D ），它很容易被改写为非递归过程。
  A. 单向递归  B. 回溯递归
C. 间接递归   D. 尾递归
10. 设有一个广义表A (a)，其表尾为（ C ）。
  A．a     B．( ( ) )
C．（）   D．(a)
11. 对于一组广义表A( ), B(a,b), C(c,(e,f,g)), D(B,A,C), E (B, D)，其中的E是（ D ）。
  A. 线性表   B. 纯表
C. 递归表   D. 再入表
12. 在一棵树中，( C )没有前驱结点。
  A. 树枝结点  B. 叶子结点
C. 树根结点  D. 空结点
13. 在一棵具有n个结点的二叉树的第i层上(假定根结点为第0层，i大于等于0而小于等于树的高度)，最多具有( A )个结点。
  A. 2i     B. 2i+1
C. 2i-1   D. 2n
二、填空题
1. 链表与顺序表、索引表、散列表等都是数据逻辑结构的（存储）表示。
2. 队列是一种限定在表的一端插入，在另一端删除的线性表，它又被称为（先进先出）表。
3. 向一个顺序栈插入一个元素时，首先使（栈顶指针）后移一个位置，然后把待插入元素写入到这个位置上。
4. 向一个循环队列中插入元素时，需要首先移动（队尾）指针，然后再向所指位置写入新元素。
5. 在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有（1）个结点。
6. 递归工作栈起到两个作用，其一是将递归调用时的实际参数和返回地址传递给下一层递归；其二是保存本层的形式参数和（局部变量）。
7. 非空广义表的除第一个元素外其他元素组成的表称为广义表的（表尾）。
8. 广义表的深度定义为广义表括号的（重数）。
9. 一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点f的层数为（3）。假定树根结点的层数为0。
10. 在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有（6）个。
11． 一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为（6）个。
12. 在一棵高度为h的理想平衡二叉树中，最多含有（2h+1-1）个结点。假定树根结点的高度为0。
三、判断题（对/错）
1．在用单链表表示的链式队列Q中，队头指针为Q->front，队尾指针为Q->rear，则队空条件为Q->front == Q->rear。错
2递归调用算法与相同功能的非递归算法相比，主要问题在于重复计算太多，而且调用本身需要分配额外的空间和传递数据和控制，所以时间与空间开销通常都比较大。对
3将f = 1 + 1/2 + 1/3+ … + 1/n转化为递归函数时，递归部分为f (n) = f (n-1) + 1/n，递归结束条件为f (1) = 1。对
4. 一个广义表 ( (a), ( (b), c), ( ( (d) ) ) ) 的长度为3，深度为4。对
5. 当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置完成删除操作。错
6. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。对
. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。对
7. 在树的存储中，若使每个结点带有指向双亲结点的指针，这为在算法中寻双亲结点带来方便。对
8． 于一棵具有n个结点的任何二叉树，进行前序、中序或后序的任一种次序遍历的空间复杂度为O(log2n)。错
9．对具有n个结点的堆进行插入一个元素运算的时间复杂度为O(n)。对
四、运算题
1. 已知一棵树的静态双亲表示如下，其中用-1表示空指针，树根结点存于0号单元，分别求
出该树的叶子结点数、单分支结点数、两分支结点数和三分支结点数。
  序号： 0 1 2 3 4 5 6 7 8 9 10
a b c d e f g h i j k
-1 0 1 1 3 0 5 6 6 0 9
  data:
  parent:
叶子结点数： 5
单分支结点数：3
两分支结点数：2
三分支结点数：1
2. 已知一个有序表(15,26,34,39,45,56,58,63,74,76,83,94)顺序存储于一维数组a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。
34 56 58 63 94
2 1 3 4 4
元素
  比较次数
3. 假定一个线性序列为 (38,42,55,15,23,44,30,74,48，26)，根据此线性序列中元素的排列次序生成一棵二叉搜索树，求出该二叉搜索树中左子树为空的所有单支结点和右子树为空的所有单支结点，请按照结点值从小到大的次序写出。
左子树为空的所有单支结点：15,23,42,44
右子树为空的所有单支结点：30
4. 假定一组记录为(40,28,16,56,50,32,30,63,44,38)，按次序插入每个记录生成一棵AVL树，请回答插入时造成不平衡的结点个数。
插入时造成不平衡的结点个数：4
5. 已知图G=(V,E)，其中V={a,b,c,d,e}，E={，，，，，，}，请写出各结点的出度和入度。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。