计算机学院数据结构与算法
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
期末试
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
(2003级B) 计算机学院数据结构与算法分析期末
试题
中考模拟试题doc幼小衔接 数学试题 下载云南高中历年会考数学试题下载N4真题下载党史题库下载
(2003级B) 一、单项选择题（每小题 2 分，共20分） 1．以下数据结构中哪一个是线性结构？（ ） A）无向图 B）栈 C）线索二叉树 D）B+树 2．用单链表表示的链式队列的队头在链表的（ ）位置。 A）表头 B）表尾 C）表中 D）前面都正确 3．设一个栈的入栈序列是ABCD，则借助于一个栈所得到的出栈序列不可能是（ ）。 A）ABCD B）ADCB C）ACDB D）DABC 4．若串S="software"，其子串数目是（ ）。 A）8 B）37 C）36 D）7 5．在数组A中，假设每个元素的大小为3字节，行下标从0到8，列下标从0到9，从首地址为1000的位置开始以行序为主序连续存储于存储器内，则元素A[3][6]的起始地址是（ ）。 A）1099 B）1108 C）1171 D）1189 6．广义表((a,b),(c,d,e))的表尾是( )。 A）(c,d,e) B）((c,d,e)) C）(e) D）e 7．快速排序在最坏情况下的时间复杂度为（ ）。 A）O(log2n) B）O(nlog2n) C）O(n) D）O(n2) 8．对于具有n个顶点的强连图，其弧条数的最小值为（ ）。 A）n+1 B）n C）n+2 D）n-1 9．从一具有n个结点的单链表中查找其值等于k的结点时，在查找成功时平均比较次数是（ ）。 A）n B）n/2 C）(n-1)/2 D）(n+1)/2 10．在下列排序算法中，时间复杂度不受数据初始特性影响，恒为O(n2)的算法是（ ）。 A）简单选择排序 B）插入排序 C）快速排序 D）冒泡排序 二、（本题8分） 有 5个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C第一个出栈，D第二个出栈的次序有哪几个？ 三、（本题8分） 已知关键字序列{12,26,38,89,56}，试构造平衡二叉树。 四、（本题9分） 有二叉树中序序列为：ABCEFGHD；后序序列为：ABFHGEDC；请画出此二叉树。 五、（本题9分） 设用于通讯的电文仅由8个字母组成，它们在电文中出现的频率分别为0.30、0.07、0.10、0.03、0.20、0.06、0.22、0.02，试设计哈夫曼树及其编码。 六、（本题9分） 如下图所示，用Prim算法从结点1出发构造出一棵最小生成树，要求图示出每一步的变化情况。 有向图示意图 七、（本题9分） 已知哈希表地址空间是0..8，哈希函数是H(k)=k%7，采用线性探测再散列处理冲突，将序列{100,20,21,35,3,78,99,45}数据序依次存入此哈希表中，列出插入时的比较次数，并求出在等概率下的平均查找长度。 解答：哈希表及查找各关键字的比较次数如下表所示： 哈西表及查找各关键字的比较次数 哈希地址 0 1 2 3 4 5 6 7 8 关键字 21 35 100 3 78 99 20 45 比较次数 1 2 1 1 4 5 1 5 平均查找长度= 八、（本题9分） 判别下面的每个结点序列是否表示一个大顶堆，如果不是堆，请把它调整为堆。 （1）100,90,80,60,85,75,20,25,10,70,65,50 （2）100,70,50,20,90,75,60,25,10,85,65,80 九、（本题9分） 试画出表达式(a+b/c)*(d-e*f)的二叉树表示，并写出此表达式的波兰式表示及逆波兰式表示。 十、（本题10分） 二叉树以二叉链表为存储结构，写一算法以凹入表示法来表示二叉树（不用画出网格线），在每个结点后用(R)表示根结点，用(l)表示当前结点是双亲的左孩子，用(r)表示当前结点是双亲的右孩子，如下图所示： 二叉树的凹入表示法示意图 解答：根据图中所示的显示方式，二叉树的第一层输出在第一列，第二层输出在第二列，第三层输出在第三列；每行显示一个结点，从上至下是按先序遍历次序显示结点。 参考算法如下： void DisplayBTWithConcaveShape(BiTree T,int level=1,char tag='R') /* 按凹入表方式显示二叉树，level为层次数，可设根结点的层次数为1 tag表示结点类型，分为根结点'R'，双亲的左孩子'l'，双亲的右孩子'r' */ { if(T) { //空二叉树不显式，只显式非空二叉树 cout<
data<<"("<lchild,level+1,'l');//显示二叉树的左子树 DisplayBTWithConcaveShape(T->rchild,level+1,'r');//显示二叉树的右子树 } }
浙公网安备 33021202002483