石家庄铁道大学数据结构试卷卷A

第1页/共4页一、单项选择题（每小题2分，共20分）1.计算机中的算法是指解决某一问题的有限操作序列，它必须具备输入、输出、（）等5个特性。A.可行性、可移植性和可扩充性 B.可行性、有穷性和确定性C.确定性、有穷性和稳定性 D.易读性、稳定性和确定性2.循环链表的主要优点是（）。A.不再需要头指针B.已知某结点位置后能容易找到其直接前驱C.在进行插入、删除运算时能保证链表不断开D.在表中任一结点出发都能扫描整个链表3.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（）。A.q->next=s->next；s->next=p；B.s->next=p；q->next=s->next；C.p->next=s->next；s->next=q；D.s->next=q；p->next=s->next；4.判定一个顺序栈S（栈空间大小为n）为空的条件是（）。A.S->top==0 B.S->top!=0C.S->top==n D.S->top!=n5.循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）。A.(rear-front+m)%m B.rear-front+1C.rear-front-1 D.rear-front6.对一些特殊矩阵采用压缩存储的目的主要是为了（）。A.表达变得简单B.对矩阵元素的存取变得简单C.去掉矩阵中的多余元素D.减少不必要的存储空间的开销7.对二叉排序树进行（）遍历，可得到包含该二叉树所有结点的有序序列。A.层序 B.前序C.中序 D.后序8.一个无向图包含7个顶点，则这个无向图中边的总数最多是（）条。A.27 B.21C.7 D.69.当记录数目较多时，在平均情况下，（）是所有内部排序中速度最快的一种。A.希尔排序 B.堆排序C.折半插入排序 D.快速排序10.对包含33个记录的有序表做折半查找，当查找成功时至多需要比较（）次关键字、A.5 B.6C.7 D.8二、简答题（共25分）1.（8分）给出下列问题的解答过程：（1）关键字序列为{2,4,1,6,9,7}，用筛选法将其调整为一个大根堆，给出建堆的过程。（2）待排序的关键字序列为{5,3,6,10,8,1,4}，采用冒泡法实现从大到小排序，给出排序过程。2.（8分）已知一个无向图如图1所示。图1（1）请给出其邻接矩阵。（2）给出自顶点A出发的广度优先生成树。3.（9分）已知一棵二叉树的中序序列是CBDFHEGA，后序序列是CHFGEDBA。（1）画出这棵二叉树。（2）对这棵二叉树进行中序线索化，给出得到的中序线索二叉树。三、应用题（共35分）1.（12分）哈夫曼编码可以实现数据压缩，设一段文本由数字字符和空格字符组成，字符在报文中出现频率如表1所示。表1字符1234567890空格频率3121783221161279要求根据这段报文，完成如下工作：（1）构造一棵哈夫曼树。（2）哈夫曼树HT存储结构的终态如下表2所示，请填写完整。表2结点iweightparentlchildrchild13002120031700480053200620071100860091200107001190012131415161718192021（3）求各字符的哈夫曼编码(变长编码)。2.（10分）设Hash表的地址范围为0-15，对以下关键字序列构造Hash表，关键字序列为（break，case，do，float，int，main，if，else，continue，for，cin，string），Hash函数H(key)=key%13，其中key为关键字中第一字母在字母表中的序号（范围为1-26，如字母a的key值为1）。用线性探测法解决冲突，回答下列问题：（1）构造Hash表（2）求等概率下查找成功时的平均查找长度ASLsucc3.（13分）已知一有向图如图2所示。AAGFECDB516133910712564图2要求根据有向图，完成如下工作：（1）列出顶点A到其它各顶点的最短路径（采用Dijkstra算法）。（2）根据执行算法过程中各步的状态，完成最短路径求解表，如表3所示。表3终点\Di=1i=2i=3i=4i=5i=6B∞C∞D∞E13(a,e)F3(a,f)G16(a,g)S终点集{a,f}四、算法设计题（每小题10分，共20分）说明：要对用到的数据结构进行定义。1.请设计一个算法将两个递增有序的带头结