还剩5页未读，继续阅读
文本内容:
数据结构期末考试题模拟题
一、单项选择题每小题分，共分
2301、在数据结构中，从逻辑上可以把数据结构分成A动态结构和静态结构B紧凑结构和非紧凑结构C内部结构和外部结构D线性结构和非线性结构
2、线性表L=al,a2,…，an,下列说法正确的是A除了第一个和最后一个元素外，其余每个元素都有且仅有一个直接前驱和直接后继B表中诸元素的排列必须是由小到大或由大到小C每个元素都有一个直接前驱和一个直接后继D线性表中至少有一个元素
3、现有某个堆栈S,按顺序ABCD进栈，则出栈序列中不可能存在的是A DCBAB BACDC CABDD BADC
4、对于栈操作数据的原则是A先进先出B先进后出C后进后出D不分顺序
5、循环队列存储在数组A[
0.ni]中，则入队时的操作为o・A rear=rear+l Brear二rear+1%m-1C rear=rear+1%m Drear=rear+1%m+
16、数组a[
0.5,
0..6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的・连续内存单元中，则元素式5]
[5]的地址是oA1175B1180C1205D
12107、串是一种特殊的线性表，其特殊性体现在0A可以顺序存储B数据元素是一个字符C可以链接存储D数据元素可以是多个字符
8、由3个结点可以构造出种不同的二叉树A3B4C5D
69、设某棵二叉树中有2000个结点，则该二叉树的最小高度为oA9B10C11D
1210、在下列存储形式中，不是树的存储形式的是oA顺序存储表示法B双亲表示法C孩子链表表示法D孩子兄弟表示法
11、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足A只有一个叶子结点B是任意一棵二叉树C所有的结点均无右孩子D所有的结点均无左孩子
12、G是一个非连通无向图，共有20条边，则该图至少有个顶点A5B6C7D
813、适用于折半查找的表存储方式，以及元素排列要求为A链接方式存储，元素无序B链接方式存储，元素有序C顺序方式存储，元素无序D顺序方式存储，元素有序
14、设有序表的关键字序列为{1,4,6,10,18,35,42,53,67,71,78,84,92,99},当用二分查找法想找键值为84的结点时，经次比较后查找成功A2B3C4D
1215、记录的关键字序列为{7,6,8,4,3,5},采用快速排序以第一个记录为基准得到的第一次划分结果是A）5,3,6,4,7,8B）3,5,6,4,7,8C）6,4,3,5,7,8D）5,6,3,4,7,8
二、填空题（每空分，共分）
2101、一个算法的效率可分为时间效率和效率
2、二维数据A
[10]
[20]采用列序为主方式存储，每个元素占一个存储单元，且A
[0]
[0]的地址是200,则A
[6]
[12]的地址是
3、设哈夫曼树中共有n个结点，则该哈夫曼树中有个度数为1的结点
4、广义表L=（a,（b,c））,进行Tail（L）操作后的结果是
5、在散列技术中，处理冲突的两种方法是和链地址法
三、判断题（每题分，共分），对的打错的打110X
1、顺序表中在插入或删除操作时不需移动数据元素（）
2、对于单循环链表，从表中任一结点出发都能扫描表中全部结点（）
3、栈和队列都是限制存取端的线性表（）
4、任何一个递归过程都可以转换成非递归过程（）
5、N阶对称矩阵经过压缩存储后占用的存储单元是原来的1/2（）
6、满二叉树一定是完全二叉树，完全二叉树也一定是满二叉树（）
7、已知二叉树的先序序列和后序序列，则可以唯一确定一棵二叉树（）
8、强连通图的各顶点间均可到达（）
9、无向图的表示图一邻接矩阵一定是对称矩阵（）、填空分析题（每空分，共分）U!
31810、采用二分查找法对有序表进行查找总比采用顺序查找法对其进行查找要快（）
1、分析并计算下列时间复杂度for（i=l;i=n;i++）for（j=i;j〈=n;j++）s++;结果_⑴_____________
2、在双循环链表，若要在指针p所指结点前插入指针s所指的结点，则需执行下列语句:s-next=p;s-pr ior=⑵;p-prior=s;
3、下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容typedef structnode{int data;struct node*lchild;⑷；}bitree;void createbitreebitree*bt{scanf％c”，ch;if ch二二#bt=0;else{bt=bitree*malloc sizeofbitree;bt-data=ch;⑸_____;createbitree bt-rchild;
4、下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句void bubbleintr[n]{for i=l;i=n-l;i++{for exchange=O,j=0;6;j++if r[j]r[j+l]{temp=r[j+l];r[j+l]=r[j];r[j]=temp;exchange=l;}ifexchange==O return；
五、应用题（第、、、题每题分，第、题每题分，共分）
12345566321、已知一棵二叉树的中序遍历序列为FDGBHEIAC,后序遍历序列为FGDHIEBCA,请图出该二叉树（3分），并写出该二叉树的先序遍历序列（2分）
2、将下图所示的森林转换成二叉树（5分）E FM
3、已知待散列的线性表为36,15,40,63,22,散列用的一维地址空间为[
0.6],假定选用・的散列函数是H K=K mod7,若发生冲突采用线性探查法处理，试1计算出每一个元素的散列地址并在下图中填写出散列表3分2求出在查找每一个元素概率相等情况下的平均查找长度2分
4、已知序列10,18,4,3,6,12,1,9,18,8请用快速排序写出每一趟排序的结果5分
5、图右所示为一个有向图，试给出1每个顶点的入度和出度1分2邻接矩阵2分3邻接表2分4逆邻接表1分V2V4V
36、对于一组给定的权值W={7,14,3,32,5,12}，建立相应的哈夫曼树（4分）并计算其WPL值（2分）。
个人认证
优秀文档
获得点赞 0
