数据结构试题B

《数据结构试题B》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、东钿工学院（南昌校区）2011—2012学年第二学期数据结构与算法分析课程闭卷课程类别：必题号二三四五六七八九总分分数评卷人一、填空题（20分，每题2分）1、线性表是一种典型的结构。2、在一个长度为n的顺序表中删除第i个元素，则需移动个元素。3、稀疏矩阵的一般的压缩方法为。4、设二维数组intA[10][20],设A[0][0]的元素的地址为100,如果按行序优先顺序存储，则A[8][10]元索的地址为,如果按列序优先顺序存储，则A[8][10]元素的地址为。5、快速排序算法在平均情况下的时间复杂度为（用0表示法）。6、二分查找算法在平均情况下的时间复杂度为（用◎表

2、示法）。7、上图所示的二叉树中，叶结点数为—个，分支结点数为—个。8、上图所示的二叉树中，如果对其釆用指针法存储（分支结点用一个数据域和两个指针域存储，叶结点采用一个数据域存储，设数据域所占空间大小为d,指针所占空间大小为p），则该二叉树的结构性开销所占比例为o9、上图所示的二叉树中，若将其转换成完全二叉树后，则中序遍历序列为o（完全二叉树定义：从根结点起每层从左到右填充）10、图有两种常用表示方法，分别为和。二、选择题（20分，每题2分）1、（）适合从一个结点出发，在线性表中随意访问它的后继结点而不能访问它的前趋结点。（A）顺序表（B）单链表（C）循环链表（D）

3、双向链表2、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。A、0（1）B、0（n）C、0（n"2）D、0（log2n）3、栈和队列与一般的线性表的区别在于（）。A、数据元素的类型不同B、运算是否受限制C、数据元素的个数不同D、逻辑结构不同4、一个栈的入栈序列是abcde,则栈的不可能的输出序列是（）oA>edcbadecbaC>dceabD.abcde5、一个队列的入列序列是abed,则队列的输出序列是（）。A、debaB、abedC、adebD、cbda6、串是一种特殊的线性表，其特殊性体现在（）oA、可以顺序存储B、数据元素是一个字

4、符C、可以链接存储D、数据元素可以是多个字符7、广义表是线性表的推广，它们之间的区别在于（）»A、能否使用子表B、能否使用原子项C、表的长度n

5、>D、是否能为空8、如果图的边数较少，则称这个图为（）A、密集图B无向图C稀疏图D密集图有向图9、已知一棵二叉树的前序和中序序列分别为ABDECFG和DBEAFCG,则该二叉树的后序序列为（）A、DEBFGCAB、ABCDEFGC、DAEBGCFD、DBECFGA10、设某二叉树为满二叉树，其分支结点数为7,则其叶结点数为（）A、7B、8C、9D、10三、将下图示的树转换成二叉树（5分）四、设待排序文件的关键码为（&5,2,

6、1,4,7,6,3）,现用插入排序的方法对Z进行排序（按关键码值递增顺序），请给出每一趟扫描后的结果（8分）。五、假设用于通信的电文由字符集（a,b,c,d,e,f,g,h｝中的字母构成，这8个字母在电文中出现的概率分别为｛0.01,0.02,0.20,0.09,0.32,0.15,0.10,0.11｝（共10分，第一问6分，第二问4分）（1）为这8个字母设计哈夫曼编码（注：在构造哈夫曼树时将概率值小的字符放在左子树上）。（2）若用三位二进制数（0-7）对这8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少？八、已知某无向图及

7、邻接表如下图所示。（共10分；每题5分，其中前一问3分，后一问2分）（1）给出其相应的深度优先遍历结果（从A开始，用栈结构），并画出其深度优先生成树。（2）给出其相应的广度优先遍历结果（从A开始，用栈结构），并画出其广度优九、程序设计题(12分，笫一•题5分，笫二题7分)1、已知Q是一个非空队列，S是一个空栈。仅用队列和栈的ADT函数和少量工作变量编写一个算法，使得Q中的元素倒置。voidreverse(Queue&Q,Stack&S)栈的ADT函数有：boolpush(constElem&item)//入栈操作，将元素item入栈，如果入栈成功，则函数返回为tru

8、e,否则函数返回为falseboolpop(Elem&it)//出栈函数，将栈顶元素出栈并赋值给it,如果出栈成功，则函数返回为true,否则函数返回为falseboolisEmptyO//判断栈是否为空函数，如果栈为空，则函数返回为true,否则返回为false队列ADT的函数有：boolenqueue(constElem&it)//入队函数，将元素it入队，如果入队成功，函数返回为true,否则返回为falsebooldequeue(Elcm&it)//出队函数,将队首元素出队,如果出队成功,则函数返回为true,否则返回为falseboolisEmptyO