1、第1页共4页三 峡 大 学2014年研究生入学考试试题(A卷)科目代码：838 科目名称： 数据结构考试时间为3小时，卷面总分为150分答案必须写在答题纸上一、填空题 (每小题 2分，共 30分)1. 有一算法的计算次数f（n）=1000000+0.001n2+1000nlgn，则该算法的复杂度用大O表示法应该是（ ）A. O(1000000) B. O(1) C. O(n2) D. O(nlgn) 2、链表的特征是（ ）A逻辑连续,物理连续 B. 逻辑连续,物理不连续C逻辑不连续,物理连续 D. 逻辑连续,物理不一定连续3、已知链表中某结点指针为p，在其后插入一个指针s指向的新结点，则需执行
2、下列哪个指令Ap-next=s B. p-next=s; s-next=p-next;C. s-next=p-next; p-next=s; D. s-next=p-next; s-next=p;4. 设有一个顺序栈P，元素按P1,P2,P3,P4.P5顺序进栈，若5个元素的出栈顺序为P2, P3, P5, P4,P1，则顺序栈的容量至少应为（ ）。A. 2 B.3 C. 4 D.55、设有一个二维数A1010，假设A20的存放位置在1020，按行优先存储，每个元素占2空间，A55在（ ）位置。A1102 B.1100 C.1088 D.10906、已知结点的权重分别是1,2,3,3,3，则对
3、应哈弗曼树的带权路径长度为（ ）A. 26 B.27 C.28 D.307、已知某二叉树先序遍历结果为ABCDEF，中序遍历果为BCAEFD，则其后序遍历结果是（ ）.ABCDEFA B. CBFEDA C. ABDCEF D. BCEFDA8、在10个顶点的无向图的邻接表中，除头结点外，共有（ ）个链表结点。A.10 B.20 C.30 D.159. 在单链表中删除一个指定元素的复杂度是（ ）A、O(n) B. O(n2) C. O(1) D. O(nlog2n) 第2页10、在长度为100的二叉排序树中进行查找一个存在的元素，最多比较（ ）次。A. 8 B. 7 C. 6 D. 111、图
4、的广度优先遍历过程中，需要用到（ ）作为辅助数据结构保证同层结点访问的正确顺序。A、顺序表 B、链表 C、栈 D、队列12、已知待散列的线性表为（98，35，27，42，67，56），假定选用的散列函数是H（K）= K % 7，则与98冲突元素个数是（ ）A、0 B、1 C、2 D、313、快速排序最坏情况下的复杂度是（ ）A、O(n) B. O(n2) C. O(1) D. O(nlog2n) 14、下列算法中属于稳定排序的是（ ）A. 堆排序 B. 简单选择排序 C. 快速排序 D. 二分插入排序15、对于数据量不大且接近有序时，适合采用（ ）A. 堆排序 B. 直接插入排序 C. 快速排
5、序 D. 冒泡排序二、判断题题 (每题2分，共20分, 对的打，错的打)1. 数据结构的逻辑结构决定了其存储结构。（ ）2. 比较算法复杂度需在同一运行环境下的运行比较时间 （ ）3.对于最大指数很大，非零项很少的一元多项式加法适合采用链式存储结构存储。（ ）4.当队中有元素时，队尾元素不能出队。（ ）5.除了内存溢出，链栈一般不会满。（ ）6.给定二叉树先序遍历序列和后序遍历序列一般不能唯一确定树结构。（ ）7. 图的非关键活动时间可以任意安排。（ ）8. 稠密图采用邻接矩阵的存储效率要高于邻接表。（ ）9. 二分查找方法不可以对链表进行。（ ）10.当排序长度大且数据随机但不要求稳定时，最
6、适合采用堆排序算法。（ ）三、填空题 (每个空2分，共30分)1用21把钥匙试开1把锁（只有一把能开），平均需要试（ ）次。2. 15辆车依次开进了一个死胡同，但第5辆车要开走，后面需要退出（ ）辆车。3. 采用空闲单元法的循环队列容量为100，若f=25，r=47，则队长（ ），若f=55，r=25，则队长是（ ）。4. 数组A1010采用列优先存储，每个数据占4个字节，A00起始地址是2000，该数组的存储空间需要（ ）个字节；A87的存储地址是（ ）. 第3页5、设一棵完全二叉树具有1001个结点，则它有( ) 个叶子结点，有 ( )个度为2的结点，有( )个结点只有非空左子树，第4个叶
7、子结点编号是( )6. 10个顶点的无向完全图有（ ）条边，9个顶点有向完全图有（ ）条边。7. 在长度为11的递增有序表中二分查找第5个元素，需要比较（ ）次。8.稠密图适合采用（ ）存储结构，对应的最小生成树算法应该是基于 （ ）归并较好。四、计算题。（共50分）1. 建二叉排序树的序列是： 2，4，1，3，9，请画出该二叉排序树结构，并计算基于该树进行查找的平均查找长度。（10分）2. 根据下图回答问题（20分）（1）要完成该AOE网中工程，最短时间是多少？（不考虑单位）（5分）（2）上图中的关键路径是什么（用顶点序列表示）？将活动a8的时间改成5可否提前完成？（5分） （3）若忽略边的
8、权值将上图看成一个AOV网，并约定当存在多个入度为0的结点时先输出编号较小的结点，则请写出拓扑排序结果。（5分）（4）若忽略边的方向性将上图看成无向网，各边权值为经济代价，请给出该无向网的一棵最小生成树。（5分）3. 已知待排序关键字序列是38，19，50，61，32，23，11，15，14请回答下列排序问题(要求排成升序序列)：（20分）(1) 若采用直接插入排序，第二个位置前移的元素关键字是？(4分)(2) 若采用希尔排序(di5,3,1), 第二个位置前移的元素关键字是？(4分)(3) 若采用简单选择排序，第二个位置前移的元素关键字是？(4分)(4) 若采用快速排序，第二个位置前移的元素
9、关键字是？(4分)(5) 若采用堆排序，利用筛选操作建堆过程中第二次交换的两个元素关键字是？(4分)第4页五、程序题(每题10分，共20分)1. 已知x和y是整型全局变量，初值均为0，root为二叉树的根结点。（10分）void ABC(NODE *root) if ( root) ABC(root-lchild); ABC (root-rchild);if(root-lchild & root-rchild ) x +; if( root-lchild | root-rchild ) y +; （1）该算法是在二叉树哪种遍历程序基础上修改成的？（3分）（2）执行该算法后x和y中保存的值分别是
10、什么？ （4分）（3）试用x和y表示二叉树的总结点数n。 （3分）2. 算法填空，使之可以对降序序列进行二分查找,要求找到则返回元素在查找表中位置，否则返回0（5分）。int binarysearch( splist st ,int n , keytype key) /降序序列函数，st顺序表 n表长 key 关键字int mid ,low,high,find;find=0; low=1; high=n;while ( (lowstmid.key)（2） ;else if (keystmid.key) (3) ;else (4) ; /找到printf(“find st%d.key= =%dn”,mid,key); (5) ;/返回位置return(0); /*binarysearch二分查找*/
