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