2008数据结构学位考试试卷A

你一定要坚强，即使受过伤，流过泪，也能咬牙走下去。因为，人生，就是你一个人的人生。==============================================================================PAGE命运如同手中的掌纹，无论多曲折，终掌握在自己手中==============================================================科目名称：数据结构1Ｏ八-Ｏ九学年第一学期申请广州大学学士学位抽考课程试卷（A）课程名称数据结构考试形式（开/闭卷）系别专业班级学号姓名试题一二三四五六总分评卷人分值2010183220100得分考试时间：2009年1月日答题时间：120分钟考试地点：考试形式：闭卷一、单项选择题(每题1分,只有一个正确答案）分值20得分线性表的链式存储比顺序存储最有利于进行（）。A.查找 B.表尾插入或删除 C.按值插入或删除 D.表头插入或删除在一个无向图中,所有顶点的度数之和等于所有边数的（）倍。A．3 B.2 C.1 利用n个值作为叶子节点的权生成的哈夫曼树中共包含有（）个节点。A．n B.n+1 C.2×n D.2×n-1为了实现树的层次遍历算法,使用的一个辅助数据结构为（）。A．队列 B.栈 C.二叉树 D.树一个栈的输入序列是SWXYZ，则栈的不可能的输出序列是（）。A.ZYXWSB.YZXWSC.YXZSWD.SWXYZ假定一个带头节点的循环链队的队首和队尾指针分别用front和rear表示，则判断队空的条件为（）。A．front!=rearB.rear！=NULLC.front==NULLD.front==rear在一个长度为N的数组空间中，顺序存储着一个队列，该队列的队首和队尾指针分别用front和rear表示，则该队列中的元素个数为（）。A．(rear-front)%NB.(rear-front+N)%NC．(rear+N)%ND.(front+N)%N在一棵具有n个节点的二叉树的第i层上（根节点为第1层），最多具有（）个节点。A．2i B.2i+1 C.2i-1 D.2n根据n个元素建立一棵二叉搜索树时，其时间复杂度为（）。A．O(n) B.O(log2n) C.O(n2) D.O(nlog2n)n(n>1)个顶点的强连通图中至少含有（）条有向边。A．n-1 B.n C.n(n-1)/2 D.n(n-1)

输入序列为ABC，若变为CBA时，经过的栈操作为（）A.push,push,push,pop,pop,popB.push,pop,push,pop,push,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9B．11C．15D．不确定在一个表头指针为ph的单链表中，若要在指针q所指节点的后面插入一个由指针p所指向的节点，则执行（）操作。A．q->next=p->next;p->next=q;B.p->next=q->next;q=p;C．q->next=p->next;p->next=q;D.p->next=q->next;q->next=p;在一个带头节点的循环双向链表中，若要在指针p所指向的节点之后插入一个q指针所指向的节点，则需要对q->right赋值为（）。A．p->left B.p->right C.p->right->rightD.p->left->left假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，top=-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作为（）。A．a[--top]=x;B.a[top--]=x;C.a[++top]=x;D.a{top++}=x;如果一个元素序列基本有序时，则选用（）方法较快。A．直接插入排序B.直接选择排序C.堆排序D.快速排序假如一棵二叉树有3个结点,其有多少种不同的形态（）：A.4种 B.5种 C.6种 D.7种对于具有e条边的无向图，它的邻接表中有（）个边节点。A．e-1 B.e C.2(e-1) D.2e下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。A．二叉排序树B．哈夫曼树 C．AVL树 D．堆排序二叉树的_______遍历的序列是一个关键字的递增的有序序列A.先根遍历 B.中根遍历 C.后根遍历 D.层次遍历二．判断题(正确打“√”,错误打“×”)分值10得分1.线性表的特点是每个元素都有一个前驱和一个后继。()2.取线性表的第i个元素的时间与i的大小有关.()3．完全二叉树中，若一个结点没有左孩子，则它必是树叶。()4．完全二叉树的存储结构通常采用顺序存储结构。()5．将一棵树通过孩子兄弟链表转成二叉树，根结点没有左子树；()6．任何无向图都存在生成树。（）7.关键路径是AOE网中从源点到终点的最长路径。（）8.循环队列也存在空间溢出问题。（）9．在待排序数据基本有序的情况下，快速排序效果最好。（）10．（101，88，46，70，34，39，45，58，66，10）是堆。（）三．算法填空（每空2分,共18分）分值18得分1、采用快速排序算法对在A[s]~A[t]区间的关键字进行排序。voidQuickSort(intA[],ints,intt){ inti=s,j=t+1; intx=A[s]; do{ do_________;while(A[i]<x); do__________;while(A[j]>x); if(_____________) { inttemp=A[i]; A[i]=A[j];A[j]=temp; } }while(________); A[s]=A[j];A[j]=x; if(____________)QuickSort(A,s,j-1); if(____________)QuickSort(A,j+1,t);}2、统计二叉树叶子节点数intBTreeleafCount(BinTreeNode*BT) { if(BT==NULL)return_______; if(BT->left==NULLandBT->right==NULL)return________; else return____________________________________________________;}四．应用题（每题8分共32分）分值32得分下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，并画出可能的选择。(8分)2.假设一个二叉树的两种遍历如下：前序：ABFGCHDEIJLK中序：FGBHCDILJKEA画出这棵二叉树,并求其后序遍历。（8分）

3．用给出的一组权值{7，19，2，6，32，3，21，10}，构造一棵哈夫曼树，并计算其带权路径长度WPL。（要求写出哈夫曼树构造过程及WPL的计算过程）(8分）4、己知一组关键字为（32，75，29，63，48，94，25，46，18，70，19），按哈希函数H(key)=key%13和链接法处理冲突构造哈希表，并计算其平均查找长度。（8分）

五．编写算法（每小题10分,共20分）分值20得分根据函数声明voidOrderInsertList(sNode*head,intx),向带附加表头节点head的循环