DS练习
一、选择题
1：（ ）是不可分割的并且具有独立含义的最小数据单位。 （A）数据 （B）数据元素 （C）数据项 （D）数据对象
2：设某数据结构的二元组形式表示为A=（D，R），D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（ ）。
（A） 线性结构 void exam1（） { n=2;
while （n%2==0） n=n+2; printf（\）; }
（A）有限性 （B）确定性 （C）可行性 （D）算法必须有输出 4：对线性表，在下列哪种情况下应当采用链表表示？（ ） （A）经常需要随机地存取元素 （B）经常需要进行插入和删除操作
（C）表中元素需要占据一片连续的存储空间 （D）表中元素的个数不变
5：设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（ ）个元素。 （A） n-i
（B） n+l-i
（C） n-1-i
（D） i
6：在一个单链表中，若要删除指针p所指的结点的后继结点，则执行（ ）。 （A）p->next=p->next->next；
（B）p=p->next； p->next=p->next->next； （C）p->next=p->next； （D）p=p->next->next；
7：设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（ ）。 （A） n-i
（B） n-1-i
（C） n+1-i
（D） 不能确定
8：一个队列的输入序列为1，2，3，4，则其输出序列为（ ）。 （A）1 2 3 4 （B）4 3 2 1
（C）不唯一 （D）1 2 3 4或4 3 2 1 9：串是一种特殊的线性表，其特殊性表现在（ ）。 （A）可以顺序存储 （B）数据元素是一个字符 （C）可以连接存储 （D）数据元素可以是多个字符 10：二叉排序树中具有最大值的结点在树的（ ）。
（A）左子树 （B）右子树 （C）根结点 （D）不一定
（B） 树型结构 （C） 物理结构 （D） 图型结构
3：以下算法，违背了算法特性中的（ ）。
-精品
11：一组记录为｛46，79，56，38，84，40｝，则采用直接插入排序法按升序排列时第一趟排序结果是（ ）。
（A）46，79，56，38，84，40 （B）38，79，56，46，84，40
（C）38，40，46，56，84，79 （D）46，56，38，79，40，84
12：深度为k的完全二叉树至多有（ ）个结点。 （A）k （B）2k-1-1 （C）2k-1 （D）2k-1
13：在有n个结点的三叉链表中，值为非空的链域的个数（ ）。 （A）n-1 （B）2n-2 （C）n+1 （D）n+2
14：某二叉树共有叶结点15个，没有度为1的结点，则该树共有（ ）个结点。 （A）29 （B）28 （C）27 （D）不能确定
15：遍历一棵二叉树时，先遍历根结点，再遍历左子树，再遍历右子树的遍历方 法是（ ）。
（A）先序遍历 （B）中序遍历 （C）后序遍历 （D）层次遍历
16：一棵完全二叉树中根结点的编号为l，而且23号结点有左孩子但没有右孩子，则完全二叉树总共有（ ）个结点。
（A）24 （B）45 （C）46 （D）47
17：在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为（ ） （A）e （B）2e （C）n2－e （D）n2－2e
18：设有6个结点的无向图，该图至少应有（ ）条边才能确保是一个连通图。
（A）5 （B）6 （C）7 （D）8 19：可以判断一个有向图中是否含有回路的方法为（ ）。 （A）广度优先遍历 （B）深度优先遍历 （C）拓扑排序 （D）最短路径
20：在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。 （A）2 （B）3 （C）4 （D）不确定
二：判断题
1：《数据结构》是一门研究非数值计算的程序设计问题中计算机的操作对象以及 它们之间关系和操作的学科。 （ ） 2：线性表中，除第一个元素外，其他每一个元素有且仅有一个直接前驱；除最 后一个元素外，其他每一个元素有且仅有一个直接后继。 （ ） 3：哈夫曼编码树中没有度为1的结点。 （ ） 4：完全二叉树一定是满二叉树。 （ ） 5：对线性表进行折半查找时，必须要求线性表以链接方式存储，且结点按 关键字有序排列。 （ ） 6：对矩阵进行压缩存储主要是是为了操作方便。 （ ） 7：栈是一种先进先出的线性表。 （ ） 8：有向图中，所有结点的出度之和等于入度之和。 （ ）
-精品
9：当待排序记录的关键字均不相同时，排序的结果是唯一的，否则排序的结果不一定唯一。 （ ）
10：图的邻接表是一种顺序分配和链式分配相结合的存储方法。 （ ）
三、综合题
1：写出下列左图稀疏矩阵的三元组顺序表（三元组以行序为主序排列，行列号从1开始）。
2：已知二叉排序树的各结点的值依次是1-9，请标出上面右图树中各结点的值。 3：根据以下邻接表给出其对应的图形结构和邻接矩阵的存储形式。下左图 4：二叉树的后序和中序序列如下，构造出该二叉树，并写出其前序序列。 后序序列：ABCDEFG 中序序列：ACBGEDF
5：一组待排序序列为｛98，88，78，38，18，28｝，给出采用选择排序法按升序排序的全过程。 6：用克鲁斯卡尔算法求下面右图带权无向图的最小生成树。
7： 1）给定权值（4，3，16，9，22，10，5），构造相应的哈夫曼树。
2）设上述权值分别代表7个字母A、B、C、D、E、F和H出现的频率，试为这7个字母设计哈夫曼编码（左分支上标以1，右分支上标以0）。
8：下表是某计算机专业前4个学期的相关课程及其先修课程状况，利用所学知识根据表中内容
排出课程表，要求每门课程都不能与其先修课程在同一学期开设。
课程代码 C1 C2 C3 C4 C5 C6 C7 课程名称 高等数学 程序设计基础 离散数学 数据结构 高级语言程序设计 编译方法 操作系统 先修课程 C1， C2 C3， C2 C2 C5， C4 C4， C9 -精品
C8 C9 普通物理 计算机原理 C1 C8 四、算法设计题
1：建立顺序表存储线性表中的数据，要求设计算法ListInsert在顺序表L中的第i个元素前插入新的元素e。
顺序表的存储结构定义如下： Typedef struct { int data[MAXSIZE]; int last; }SeqList; 2：某线性表包含10个数据：（10,20,30,40,50,60,70,80,90,100），要求 设计算法CreateList建立单链表存储数据； 单链表结点的存储结构描述： struct node /*定义单链表结点类型*/ { int data; struct node *next; /*指向后继结点*/ }； 3：设计算法Treehigh确定某二叉树T（指向二叉树根结点的指针）的深度。 二叉树结点的类型定义如下: typedef struct node { int data; struct node *lchild,*rchild; }BTNode; BTNode *T; 4：写出折半查找算法BinarySearch，返回kx在有序表L（升序排序）中的位序。 查找表L定义如下： typedef struct { int data[MaxSize+1]; int length； }SqList； SqList L； （假设数据存放在L.data[1]-L.data[n]中） 5：写出快速排序算法QuickSort，实现待排序表L按关键字的由小到大排序。 待排序的顺序表L类型定义如下： #define MAXSIZE 100 typedef int KeyType; /*定义关键字类型*/ typedef struct { KeyType key; /*关键字项*/ InfoType otherinfo; /*其他数据项,类型为InfoType*/ }ElemType; /*排序的数据类型定义*/ typedef struct { ElemType Data[MAXSIZE+1]; -精品
int length; }SqList; SqList L； （假设数据存放在L.data[1]-L.data[n]中）
-精品
数据结构期末练习
