数据结构期末练习

《数据结构期末练习》由会员分享，可在线阅读，更多相关《数据结构期末练习（4页珍藏版）》请在装配图网上搜索。

1、DS练习一、选择题1：（ ）是不可分割的并且具有独立含义的最小数据单位。（A）数据 （B）数据元素 （C）数据项 （D）数据对象2：设某数据结构的二元组形式表示为A=（D，R），D=01，02，03，04，05，06，07，08，09，R=r，r=，则数据结构A是（ ）。（A） 线性结构（B） 树型结构（C） 物理结构（D） 图型结构3：以下算法，违背了算法特性中的（ ）。void exam1（） n=2; while （n%2=0） n=n+2; printf（%dn,n）; （A）有限性 （B）确定性 （C）可行性 （D）算法必须有输出4：对线性表，在下列哪种情况下应当采用链表表示？（ ）

2、 （A）经常需要随机地存取元素 （B）经常需要进行插入和删除操作（C）表中元素需要占据一片连续的存储空间 （D）表中元素的个数不变5：设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（ ）个元素。 （A） n-i（B） n+l-i（C） n-1-i（D） i6：在一个单链表中，若要删除指针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，则输出序列中第

3、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）不一定11：一组记录为46，79，56，38，84，40，则采用直接插入排序法按升序排列时第一趟排序结果是（）。（A

4、）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，8412：深度为k的完全二叉树至多有（ ）个结点。 （A）k （B）2k-1-1 （C）2k-1 （D）2k-113：在有n个结点的三叉链表中，值为非空的链域的个数（ ）。（A）n-1 （B）2n-2 （C）n+1 （D）n+214：某二叉树共有叶结点15个，没有度为1的结点，则该树共有（ ）个结点。 （A）29 （B）28 （C）27 （D）不能确定15：遍历一棵二叉树时，先遍历根结点，再遍历左子树，再遍历右子树的遍历方法是（ ）。（A

5、）先序遍历 （B）中序遍历 （C）后序遍历 （D）层次遍历16：一棵完全二叉树中根结点的编号为l，而且23号结点有左孩子但没有右孩子，则完全二叉树总共有（ ）个结点。（A）24 （B）45 （C）46 （D）4717：在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为（ ） （A）e （B）2e （C）n2e （D）n22e18：设有6个结点的无向图，该图至少应有（ ）条边才能确保是一个连通图。（A）5 （B）6 （C）7 （D）819：可以判断一个有向图中是否含有回路的方法为（ ）。（A）广度优先遍历 （B）深度优先遍历 （C）拓扑排序 （D）最短路径 20：在一个无向图中，所有顶点的

6、度数之和等于所有边数的（ ）倍。（A）2 （B）3 （C）4 （D）不确定二：判断题 1：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间关系和操作的学科。 （ ）2：线性表中，除第一个元素外，其他每一个元素有且仅有一个直接前驱；除最后一个元素外，其他每一个元素有且仅有一个直接后继。 （ ）3：哈夫曼编码树中没有度为1的结点。 （ ）4：完全二叉树一定是满二叉树。 （ ）5：对线性表进行折半查找时，必须要求线性表以链接方式存储，且结点按关键字有序排列。 （ ）6：对矩阵进行压缩存储主要是是为了操作方便。 （ ）7：栈是一种先进先出的线性表。 （ ）8：有向图中，所有结点

7、的出度之和等于入度之和。 （ ）9：当待排序记录的关键字均不相同时，排序的结果是唯一的，否则排序的结果不一定唯一。 （ ） 10：图的邻接表是一种顺序分配和链式分配相结合的存储方法。 （ ）三、综合题1：写出下列左图稀疏矩阵的三元组顺序表（三元组以行序为主序排列，行列号从1开始）。2：已知二叉排序树的各结点的值依次是1-9，请标出上面右图树中各结点的值。3：根据以下邻接表给出其对应的图形结构和邻接矩阵的存储形式。下左图4：二叉树的后序和中序序列如下，构造出该二叉树，并写出其前序序列。后序序列：ABCDEFG 中序序列：ACBGEDF 5：一组待排序序列为98，88，78，38，18，28，给出

8、采用选择排序法按升序排序的全过程。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离散数学C1， C2C4数据结构C3， C2C5高级语言程序设计C2C6编译方法C5， C4C7操作系统C

9、4， C9C8普通物理C1C9计算机原理C8四、算法设计题1：建立顺序表存储线性表中的数据，要求设计算法ListInsert在顺序表L中的第i个元素前插入新的元素e。顺序表的存储结构定义如下：Typedef struct int dataMAXSIZE; int last;SeqList;2：某线性表包含10个数据：（10,20,30,40,50,60,70,80,90,100），要求设计算法CreateList建立单链表存储数据；单链表结点的存储结构描述：struct node /*定义单链表结点类型*/ int data; struct node *next; /*指向后继结点*/； 3：

10、设计算法Treehigh确定某二叉树T（指向二叉树根结点的指针）的深度。二叉树结点的类型定义如下:typedef struct node int data; struct node *lchild,*rchild;BTNode;BTNode *T;4：写出折半查找算法BinarySearch，返回kx在有序表L（升序排序）中的位序。查找表L定义如下： typedef struct int dataMaxSize+1; int length； SqList；SqList L；（假设数据存放在L.data1-L.datan中）5：写出快速排序算法QuickSort，实现待排序表L按关键字的由小到大排序。待排序的顺序表L类型定义如下：#define MAXSIZE 100 typedef int KeyType; /*定义关键字类型*/typedef struct KeyType key; /*关键字项*/ InfoType otherinfo; /*其他数据项,类型为InfoType*/ ElemType; /*排序的数据类型定义*/typedef struct ElemType DataMAXSIZE+1; int length; SqList;SqList L；（假设数据存放在L.data1-L.datan中）