数据结构试题4

1、计算机科学与技术专业数据结构试题一、单选（每小题2分，共20分）1、向顺序栈中压入新元素时，应当（）oA.先移动栈顶指针，再存入元素B.先存入元素，再移动栈顶指针D.同时进行C.先后次序无关紧要2、设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（）。A. O（nlog2e）C.O（ne）3、一个对象序列的排序码为46,79,56,对象为基准而得到的第一次划分结果为（A.38,46,79,56,40,84C.40,38,46,56,79,844、线性链表不具有的特点是（）。A.随机访问C.插入与删除时不必移动元素B. O（n+e）D.0（112）38,40

2、,84,采用快速排序以位于最左位置的）。B.38,79,56,46,40,84D,38,46,56,79,40,84B.不必事先估计所需存储空间大小D.所需空间与线性表长度成正比5、设有一个10阶的对称矩阵采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B口中，A00存入B0中,则A85在B中（）位置。A.32B.33C.41D.656、设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（）个。C.n+1）O（根的层次号为0）C.6D.n+2D.5）方法比较次数A.n-1B.n7、具有65个结点的完全二叉树的高度为（A.8B.78、若待排序对象序列

3、在排序前已按其排序码递增顺序排序，则采用（最少。A.直接插入排序B.快速排序C.归并排序D.直接选择排序9、在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。A.3B.2C.1D.1/210、对有14个数据元素的有序表R14进行折半搜索，搜索到R3的关键码等于给定值,此时元素比较顺序依次为（）oA.R0,Rl,R2,R3C.R6,R2,R4,R3B.R0,R13,R2,R3D.R6,R4,R2,R3二、判断题(每小题1分，共10分)()11、数据的基本单位是数据项。()12、带权的无向连通图的最小生成树是唯一的。()13、数组元素之间的关系，既不是线性的，也不是树形的。()14、对于有n

4、个对象的待排序序列进行归并排序，所需平均时间为O(nlog2n)。()15、用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。()16、在霍夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应当特殊处理。()17、线性表采用顺序存储表示时，必须占用一片连续的存储单元。()18、由树转化成二叉树，其根的右子女指针总是空的。()19、直接选择排序是一种稳定的排序方法。()20、装载因子是散列表的一个重要参数，它反映了散列表的装满程度。三、阅读理解题(说明下列递归过程的功能。10分)21、voidunknown(BiiiTreeNode*T,intI)指针T是完全二叉树的根指针

5、。if(T!=NULL)cout<<T>data«”,"«I«endl；unknow(T>leftCluld,i+1)：unknow(T>rightChild,i+1)；主程序调用方式unknown(BT.Root,0)；二叉树根结点的层次号为0,其他结点的层次号等于其双亲的层次号加一。四、简答题（共35分）22、对下面的有向图从顶点V1开始进行遍历，试画出遍历得到的DFS生成森林和BFS生成森林。（各4分，共8分）23、已知某二叉树的前序序列为EBADCFHGI,中序序歹U为ABCDEFGHL请给出二叉树的后序序列。（构造

6、出二叉树7分，后序遍历3分，共10分）24、将关键码53,78,65,17,87,09,81,45,23依次插入到一棵初始为空的二叉搜索树中，画出每插入一个关键码后的二叉搜索树。（9分）25、设有150个记录要存储到散列表中，并利用线性探杳法解决冲突，要求找到所需记录的平均比较次数不超过2次。试问散列表需要设计多大？（设a是散列表的装载因子，则有ASLsucc=（1+1/（1-a）/2）。（8分）五、综合算法题（每小题5分，共15分）一个一维整数数组Am中有n（nWm）个非空整数，它们相继存放于数组的前端并已按非递减顺序排列，针对下列三种情况，分别编写相应的函数。26、在数组A中插入一个新的整

7、数x,并使得插入后仍保持非递减有序。要求x插在值相等的整数后面。（5分）voidIiisertSort（intA,mtm,int&n,intx）27、将数组中所有整数原地逆置，即利用原数组空间将数组中全部元素反转。（5分）voidreverse（intA口，intn）)28、删除数组中多余的值相等的整数(只保留第一次出现的那个整数)。(5分)VoiddelDuplicate（mtA口，int&n）)六、填空题(每空2分，共10分)29、设有一个带表头结点的双向循环链表L,每个结点有4个数据成员：指向前驱结点的指针pho、指向后继结点的指针next、存放数据的成员data和访问频

8、度freq。所有结点的freq初始时都为0o每当在链表上进行一次L.Locate(x)操作时，令元素值x的结点的访问频度freq加1,并将该结点前移，链接到现它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。函数中有些语句缺失，请将它们补上。(每一个空2分，共10分)template<classType>voidDblList<Type>：Locate(Type&x)DblNode<Type>*p=first->next;Wliile(p!=frist&&)p=->

9、next;If(p!=first)链表中存在x；该结点的访问频度加1DblNode-<Type>*cunent=p;从链表中摘下这个结点Current-pnor->next=current今next;Current-next->prior=currentfprior;P=cunent->prior;寻找重新插入的位置Wliile(p!=first&&)P=p玲prioi;Current->next=；插入在p之后Current->piioi-p;P->next->piior=current;P->next=;)没找到e

10、lsecout<v”Sorry.Notfind!n”;缺失的内容为:计算机专业数据结构试题答案及评分标准一、单选题（每个2分，共20分）1、A2、B3、C4、A6、C7、C8、A9、B5、C10、C二、判断题（每个1分，共10分）11、X12、X16、X17、V13、J18、V14、V19、X15、X20、J三、阅读理解题（说明下列递归过程的功能。10分）21、以前序顺序输出用二叉链表表示的二叉树各结点的数据和结点的层次号。（每一个下划线标明的概念给2分）四、简答题（共35分）22、遍历得到的DFS生成森林和BFS生成森林如下：（各4分，共8分）V6V7BFS生成森林23、构造出的二叉树

11、如下:24、插入如下（9分）评分标准：除根之外,53每插一个正确得1分,全对给9分。65875325、则有ASLsucc=2L1解得aW3又有a=7=7W3，则m225。（8分）五、综合算法题（每题5分，共15分）26、插入函数如下:voidIiisertSoit(mtA,mtm,mt&n,mtx)if(n<m)mtLj;for(i=0;i<n&&Ai<=;i+;)for(j=n-l；j>=I；j")Aj+l=Aj;AI=x；n+；elsecerr«”数组已满，不能插入！"v<endl;exit();27、逆置函数如下：voidreverse(mtA,mtn)intmid=n/2,Ltemp;for(i=0;i<nud;i+)temp=Ai;Ai=An-i-l;An-i-l=temp;28、删除函数如下：VoiddelDuplicate(intA,int