计算机软件基础期中考试试题.pdf

B 卷1 2006 2007 学年第一 学期计算机软件技术基础抽查试卷注意：1、本试卷共 4 页；2、考试时间120 分钟 3、姓名、学号必须写在指定地方阅卷负责人签名：题号一二三四五六七八总 分得分一、填空题(15230 分)1 某完全二叉树共有700 个节点，那么该二叉树的高度为_，叶子节点数目为_。2.已知一有向图的邻接矩阵如下图所示（各顶点依次编号为1，2，3，4，5，6）：A=那么该图 _是 _（是否）为连通图。编号为3 的顶点的出度为_；入度为 _。如 果 从 编 号 为1 的 顶 点 出 发 对 该 图 进 行 深 度 优 先 遍 历，其 得 到 的 遍 历 序 列 为_；如果从编号为3 的顶点出发对该图进行广度优先遍历，其得到的遍历序列_。3设三个元素的入栈序列为b，c，a，那么不可能的出栈序列为_。4.一个顺序存储的循环队列最大能存储的元素数目是100，那么设队头指针(约定为指向队头元素前一位置)和队尾指针的值分别是13 和 89，那么队列中实际存储元素的个数是_；若队头指针和队尾指针的值分别是89 和 13，那么队列中实际存储元素的个数是_。5.顺序查找一个具有n个元素的线性表，其时间复杂度为_；二分查找一个具有n 个元素的顺序存储的线性表，其时间复杂度为_。6.已知一二叉树的先序遍历和中序遍历得到的序列为ABECFGHD 和 EBAFHGCD，那么该二叉树的后序遍历得到的序列是_。7.快速排序的平均时间复杂度为_；而当初始数据的关键字有序时，那么快速排序的时间复杂度为_。二、选择题（8324 分）1顺序存储队列Q 的入队操作可描述为：AQ.Vrear+=x BQ.V+rear=x CQ.VQ.rear+=x DQ.V+Q.rear=x 2已知某二叉树度为1 的结点数是100，总结点数是199，那么该二叉树的叶子结点数是：A49 B50 C51 D52 3设 T 为 Huffman 树，它有6 个树叶，且各树叶的权分别为2，3，4，5，6，7。那么该树的非叶子结点的权之和为：A63 B70 C68 D69 4一棵二叉树的顺序存储结构如下图所示，若中序遍历该二叉树，则遍历次序为：A B C D E F G H AABDEGCFH B DBEGACHF CABCDEFGH D DGEBHFCA 5从未排序序列中挑选元素，并将其放入已排序序列中，此排序方法称为：A插入排序B选择排序C冒泡排序D快速排序6若一个有向完全图有n 个顶点，那么该有向图的弧的数目是：An!Bn!/2 Cn*(n-1)Dn*(n-1)/2 7某有序表的关键字分别为：13，33，36，58，70，75，88，90，96，102。那么利用折半查找算法进行查找时的平均查找长度为：A2.0 B2.9 C2.5 D3.0 8利用一组关键字（20，15，10，50，60，30，17，53，13）构成二叉排序树，那么该二叉树的平均查找长度是：A20/9 B2 C25/9 D 16/9 阅卷人得分0 1 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 阅卷人得分三峡大学试卷纸教学班号序号学号姓名命题教师审题教师.试题不要超过密封线.B 卷2 三、简答题(6+1016 分)1已知一组数据元素为（54，46，75，18，27，15，39，67，88）。写出分别利用选择排序、插入排序、冒泡排序、快速排序以及2 路归并排序的第一趟 排序结果（只需要写出结果）。2 假定一个表为(6,17,22,1,14,8,11,9,28)，散列空间为 0 10，采用除留余数法构造表，哈希函数为 H(K)=K MOD 11，分别用线性探测法以及链地址法解决地址冲突，试画出在这两种方法下得到的哈希表以及等概率情况下的平均查找长度（只需要写出结果）。四、(10 分)二叉树定义如下：typedef struct btnode int data;/*存储数据信息*/struct btnode*lchild,*rchild;/*左、右孩子节点指针*/BTNODE;设二叉树T 是一棵二叉排序树，试设计一个算法，实现在T 中查找数据信息为x 的结点，如果找不到，则给出查找失败信息；否则返回该结点指针。部分代码已经给出，请把程序补充完整。BTNODE*SearchNode(BTNODE*T)BTNODE*p;p=T;/*变量初始化*/*查找过程*/while(_)if(_)/*找到*/return p;else if(_)_;else _;printf(“查找失败 n”);exit(1);阅卷人得分阅卷人得分B 卷3 五、（共 10 分）线性表定义如下：typedef struct list int key;/*关键字*/ohtertype info;/*其他信息*/LIST;用 C 语言编程实现在一个顺序存储的递增有序线性表中进行二分查找的递归 算法，已知被查找元素的关键字为x,要求返回该元素在顺序线性表中的位置。部分源代码已经给出，请把程序补充完整。/*程序开始*/int binsearchList(LIST AN,int low,int high,int x)int mid;if(_)mid=(low+high)/2;if(_)return mid;else if(_)/*左边查找*/_;else/*右边查找*/_;else/*查找失败*/return-1;六、（共 10 分）线性表定义如下：typedef struct list int AN;/*数据信息*/int len;/*线性表长度*/LIST;设 LA 和 LB 为两个顺序存储的线性表，且元素按非递减排序，写出算法将其合并为LC，且 LC 中元素也按非递减排序。void merge(LIST LA,LIST LB,LIST LC)int i,j,t;i=0;j=0;t=0;_;/*计算 LC 的表长*/while(_)/*两个表中元素都没有合并完毕*/if(LA.Ai=LB.Aj)_;else _;/*某一个表中元素还没有合并完毕*/if(i=LA.len-1)for(;i=LA.len-1;i+)LC.At+=LA.Ai+;else _。阅卷人得分阅卷人得分