1、2013年全国硕士研究生统一入学考试自命题试题（副卷）*学科与专业名称：计算机系统结构、计算机软件与理论、计算机应用技术、软件工程考试科目代码与名称：834 计算机学科与技术基础综合考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。 一. 选择题(每题2分，共30分)1在数据结构中，从逻辑上可以把数据分为（ ）。A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构C. 线性结构和非线性结构 D. 内部结构和外部结构2. 设某无向图中有n个顶点e条边，则该无向图中所有顶点的度之和为（ ）。An B. e C. 2n D. 2e3. 在内部排序中,排序时不稳定的有( )。A. 插入
2、排序 B. 冒泡排序 C. 快速排序 D. 归并排序4. 在循环队列中，若front与rear 分别表示队头元素和队尾元素的位置，则判断循环队列空的条件是( ) 。 Afront=rear+1 Brear=front+1 Cfront=rear Dfront=0 5. 设单链表中指针p指着结点A,若要删除A之后的结点(若存在),则需要修改指针的操作为( )。A. p-next=p-next-next B. p=p-nextC. p=p-next-next D. p-next=p6. 最坏情况下堆排序的时间复杂度是( )。A. O(log2n) B. O(log2n2) C. O(nlog2n)
3、 D. O(n2)7. 设使用的邻接表表示某有向图，则顶点vj在表结点中出现的次数等于（ ）。 A. 顶点vj的度 B. 顶点vj的出度 C. 顶点vj的入度 D. 无法确定8树最适合用来表示（ ）。A有序数据元素 B 无序数据元素C元素之间具有分支层次关系的数据 D元素之间无联系的数据9具有n个顶点的连通图至少应有（ ）条边。An-1 Bn Cn(n-1)/2 D2n10. 时间复杂度不受数据初始状态影响而恒定为O(nlog2n）的是（ ）。 A堆排序 B冒泡排序 C希尔排序 D快速排序考试科目： 计算机学科与技术基础综合 共 6 页，第 1 页11任何一颗二叉树的叶子结点在前序、中序、后序
4、遍历序列中的相对次序（ ）。 A不变 B发生改变 C不能确定 D以上全不对12. 一组记录（50，40，95，20，15，70，60，45，80）进行冒泡排序时，第一趟需进行相邻记录的交换的次数为（ ）。 A.5 B. 6 C. 7 D.813. 循环队列中是否可以插入下一个元素 （ ）。 A. 与曾经进行过多少次插入操作有关. B. 只与队尾指针的值有关,与队头指针的值无关. C. 只与数组大小有关,与队首指针和队尾指针的值无关 D. 与队头指针和队尾指针的值有关.14. 某二叉树的先序遍历序列为 abdgcefh, 中序遍历序列为 dgbaechf， 则它的左子树的结点数目为（ ）。A3
5、B4 C5 D615. 对于元素是整数( 占2个字节)的对称矩阵A,采用以行序为主的压缩存储方式( 下三角),若A00的地址是400, 则元素A85的存储地址是（ C ）。 A.440 B. 480 C.482 D. 582二填空题(每题2分，共20分)1稀疏矩阵一般的压缩存储方法主要有两种，即 和 。2线性结构中元素之间存在 的关系，树形结构中元素之间存在 的关系。3由n个权值构成的哈夫曼树共有 个结点。4在散列表(hash)查找中，评判一个散列函数优劣的两个主要条件是： 和 。5线索二叉树的左线索指向 ，右线索指向 。6在一棵二叉树中，度为零的结点的个数为n0，度为2 的结点的个数为n2，
6、则该二叉树有 个叶子结点。7有一个10090的稀疏矩阵，非0元素有10，设每个整型数占2个字节，则用三元组表示该矩阵时，所需的字节数是 。8带头结点的循环单链表L为空的条件是 。9设给定权值集合w=9,2,5,7 ，对应huffman树的加权路径长度WPL为 。10若某记录序列的关键字序列是（50，40，95，20，15，70），用简单选择法进行排序，第一次收集的结果是 。考试科目： 计算机学科与技术基础综合 共6 页，第 2 页三判断题（每题1分，共10分，正确的选t，错误的选f）1采用邻接表存储的图的深度优先遍历相当于树的中序遍历。（ ）2无向图的邻接矩阵一定是对称的。（ ）3线性表中的每
7、一个元素都有一个前驱和后继元素。（ ）4B和B+树都能有效地支持随机查找。（ ）5拓扑排序是按AOE网中每个结点事件的最早发生事件对结点进行排序。 （ ）6一颗满二叉树同时又是一颗平衡树。（ ）7对初始堆进行层次遍历可以得到一个有序序列。（ ）8. 冒泡排序是稳定的。( ) 9. 哈夫曼树中权值最小的结点离跟最近。（ ）10带权无向图的最小生成树是唯一的。( )四. 简答题（50分）1. 对图1.所示的有向带权图，使用Dijkstra（迪杰斯特拉）算法求出从顶点0到其余各顶点的最短路径， 要求写出过程。（10 分）41010030502060103201 图 1.2. 设使用堆排序法对关键字序
8、列 T=(10, 27, 5, 50, 60, 7, 40, 43, 75）进行排序：（10 分）（1） 画出初始大根堆对应的完全二叉树（2） 写出大根堆序列（3） 画出第一趟排序后新堆对应的完全二叉树3. 简述下列算法的功能。（6分）typedef struct BiTNodeint data;Struct BiTNode *lchild;Struct BiTNode *rchild;BiTNode,*BiTree;int func(BiTree T)考试科目： 计算机学科与技术基础综合 共6 页，第 3 页 if (TNULL) return(0);else if (T-data = 0)
9、 return(1func(T-lchild)+ func(T-rchild); elsereturn(func(T-lchild)+ func(T-rchild); 4. 使用Prime算法构造出图1所示的图G的一棵最小生成树（要求写出构造过程）。（10分）16 v1v2611211963314v6v35v5v418 图15. 假设二叉树采用顺序存储结构，如图2所示。 （6分）（1） 画出二叉树表示（2） 写出先序遍历，中序遍历，后序遍历的结果ABCDEFGHI图 26设关键字序列为（64, 5, 95, 53, 18, 25, 65, 27, 16），散列函数为H(key)=key%7，采
10、用链地址法解决冲突，请回答：（8分）（1） 画出散列表示意图（用头插法向单链表中插入结点）（2） 查找关键字95时，需要依次与哪些关键字比较（3） 求等概率下查找成功的平均查找长度五算法填空，（每空2分,共18分）1. 设计一个函数功能为：在带头结点的单链表中删除值最小的元素。请将代码补充完整。考试科目： 计算机学科与技术基础综合 共 6 页，第 4 页typedef int DataType;typedef struct Node DataType data;struct Node * next;LinkList;void deleteMin(LinkList *L)LinkList *p=
11、L-next,*q;q=p;while( )if( p-data data)q=p; ; if(!q) return; p=L; while(p-next!=q)p=p-next; ; ; 2 以下程序使用冒泡排序法对存放在a1，a2，an中的序列进行排序，完成程序中的空格部分，其中n是元素个数，要求按升序排列。 typedef struct int key; infotype otherinfo;Node;void bsort (Node a , int n) NODE temp; int i,j,flag; for(j=1; ;j+); flag=0; for(i=1; ;i+) if(ai.keyai+1.key)flag=1; temp=ai; ; ;if( )break;考试科目： 计算机学科与技术基础综合 共 6 页，第 5 页 .六编写算法（22分）1设计在顺序有序表中实现折半查找的算法。（10分） 2设计AOV-网拓扑排序的算法（12分）考试科目： 计算机学科与技术基础综合 共 6 页，第 6 页
