大学计算机软件技术基础考试技术复习题

软件技术基础复习题西电软件技术基础考试题一、填空题（每空2分，共30分）1．只有掌握了模块的内部结构，才能对模块进行__________测试。

白盒法2．软件设计可分为总体设计和__________两步。

详细设计3．文档是计算机__________的重要组成部分。

软件4．数据在计算机存储器中的存在形式称为_________。

数据的存储结构5．程序段“i=1;while(i=n) i=i*10;”的时间复杂度T(n)= ___________。

O(log10n) 6．在一个长度为n的单链表L中，删除链表中*p的直接前趋结点的时间复杂度为_________。

O(n) 7．设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是_____ r-next=s ______；r=s; r-next=null;8．循环队列sq中，用数组sq.elem［0..25］存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前sq.front 为20，sq.rear为12，则当前队列中的元素个数为____________。

18 (12-20+26)%26=1829．对称方阵中有近半的元素重复，若为每一对元素只分配一个存储空间，则可将n个元素压缩存储到___________个元素的存储空间中。

n(n+1)/210．将一棵树转换为二叉树，该二叉树的特点是_________________。

没有右子树11．具有n个结点的二叉树中,一共有2n个指针域,其中只有________个用来指向结点的左右孩子，其余的________个指针域为NULL。

n-1 n+112．一个具有n个顶点的完全无向图的边数为________。

一个具有n个顶点的完全有向图的弧的个数为________。

n(n-1)/2 n(n-1)13．对表长为9000的分块有序数据表进行分块查找，假设每一块的长度均为15，且以顺序查找法对索引表进行查找确定块，块内也采用顺序查找法。

软件技术基础总复习题及参考答案软件技术基础总复习题及参考答案一、选择题1、线性表若是采用链式存储结构时，要求内存中可用存储单元的地址 D 。

A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以2、栈和队列都是B 。

A、顺序存贮的线性结构B、限制存取点的线性结构C、链接存贮的线性结构D、限制存取点的非线性结构3、与线性表的链接存贮不相符合的特性是 C 。

A、便于插、删运算B、存贮空间动态分配C、需要连续的存贮空间D、只能顺序查找4、设二叉树的根为第一层，则第i 层上的结点数最多有B。

A、２i B、２i +1D、２i -1C、２-１i 5、如将一棵有n 个结点的完全二叉树按顺序存放方式，存放在下标编号为0, 1,…, n-1 的一维数组中，设某结点下标为k(k>0)，则其双亲结点的下标是A。

A、(k-1)/2B、(k+1)/2C、k/2D、k-16、权值分别为3,8,6,2,5 的叶子结点生成一棵霍夫曼树，它的带权路径长度为A。

A、53 B、48 C、72 D、247、设I 和O 分别表示入栈和出栈操作，栈的初态和终态都为空，则下列操作序列合法的有_ D_ _。

A、IOIOOIOIB、IOOIOIIOC、IIIOIOIOOD、IIOIIOOO 8、二叉树的前序序列为EFHIGJK，中序序列为HFIEJKG，则二叉树的根为C 。

A、K B、G C、E D、H 9、对有序表{ -1, 0, 1, 3, 4, 6, 8, 10, 12 }进行折半查找，则查找12 需要比较的次数为 B 。

A、3 B、4 C、5 D、6 10、在一个单链表中，若q 结点是p 结点的前驱结点，若在q 与p 之间插入结点s，则执行 D 。

A、s→link = p→link; p→link = s; B、p→link= s; s→link = q; C、p→link = s→link; s→link = p; D、q→link = s; s→lin k = p; 11、一个栈的入栈序列为a，b，c，则出栈序列不可能的是C 。

《计算机软件基础》复习题库(带答案)1.线性表的链式存储结构与顺序存储结构相比优点是 CD 。

A. 所有的操作算法实现简单B. 便于随机存取C. 便于插入和删除D. 便于利用零散的存储器空间2.线性表是具有n 个 C 的有限序列。

A. 表元素B. 字符C. 数据元素D. 数据项E. 信息项3.若长度为n 的线性表采用顺序存储结构，在其第I 个位置插入一个新元素的算法的时间复杂度为 C 。

（1≤I ≤n+1） A. O(0) B. O(1)C. O(n)D. O(n 2)4.设A 是一个线性表(a 1,a 2,…,a n )，采用顺序存储结构，则在等概率的前提下，平均每插入平均每删除一个元素需要移动的元素个数为若元素插在a i 与a i+1之间(0≤I ≤n-1)的概率为)1()(2+-n ni n ，则平均每插入一 ； A. 21-n B. 2n C. 312+n D. 413+n 5.下列函数中，按它们在∞→n 时的无穷大阶数，最大的是 D 。

A. logn B. nlognC. 2n/2D. n!6.A. s->next=p+1; p->next=s;B. (*p).next=s; (*s).next=(*p).next;C. s->next=p->next; p->next=s->next;D. s->next=p->next; p->next=s;7.将两个各有n 个元素的有序表归并为一个有序表时，其最少的比较次数是 A 。

A. nB. 2n-1C. n-1D. 2n8.下面的程序段是合并两个无头结点链表(ha 和 hb)为一个无头结点链表ha 的过程，作为参数的两个链表都是按结点的data域由大到小链接的。

合并后新链表的结点仍按此方式链接。

请填写下述空框，使程序能正确运行。

#define NULL 0typedef struct node{int data;struct node *next;}node, linklisttype;void combine(linklisttype *ha, linklisttype *hb){linklisttype *h, *p;h = (linklisttype *)malloc(sizeof(linklisttype));h->next = NULL;p = h;while(ha != NULL && hb != NULL)if(ha->data>=hb->data){ /*较大的元素先插入*/p->next = (1) ;p = (2) ;(3) ;}else{p->next = (4) ;p = (5) ;(6) ;}if(ha==NULL) (7) ;if(hb==NULL) (8) ;ha = h->next;free(h);}参考答案：(1) ha (2) p->next (3) ha=ha->next(4) hb (5) p->next (6) hb=hb->next(7) p->next=hb (8) p->next=ha9.如果表A中所有元素(a1,a2,…,a n)与表B的一个顺序子表(b k,b k+1,…b k+n-1)完全相同（即a1=b k,a2=b k+1,…a n=b k+n-1），则称表A包含在表B中。

第三十二次一、是非判断题（每小题1分，共10分）( 判断下列各题是否正确，如正确，在客观答题纸上对应编号选A，否则选B )1. 在程序设计中，常用一维数组来表示线性表的顺序存储空间。

( 1 )2. 软件测试的目的是为用户提供没有错误的程序。

( 2 )3. 栈顶的位置只能进行进栈操作不能进行退栈操作。

( 3 )4. 处于等待状态的进程，若其等待的事件已发生，就立即转入运行状态。

( 4 )5. 线性表若采用链式存储表示时其结点之间的存储单元地址可以不连续。

( 5 )6. 在进行插入排序时，其数据比较次数与数据的初始排列有关。

( 6 )7. 数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储结构无关，是独立于计算机的。

( 7 )8. 在操作系统中，进程最基本的特征是静态性和并发性。

( 8 )9. 软件危机是由于软件产品过多而产生的。

( 9 )10.面向过程系统需求分析使用的主要工具是数据流图和数据字典。

( 10 ) 参考答案：ABBBA AABBA二、选择题(每小题1分，共5分)1. 进程从运行状态进入就绪状态的原因可能是（11 ）。

11 (A) 时间片用完(B) 等待某一事件(C) 等待的事件已发生(D) 被选中占有处理机2. 需求分析中开发人员主要从用户那里了解（12 ）。

12 (A) 软件怎样做(B) 软件做什么(C) 输入的信息(D) 软件的测试3. 队列的操作原则是（13 ）。

13 (A) 先进后出(B) 先进先出(C) 只进不出(D) 只出不进4. 在需要经常查找结点的前驱后后继的情况下，使用（14 ）比较合适。

14 (A) 单链表(B) 循环链表(C) 双链表(D) 顺序表5. 任何两个并发进程之间（15 ）。

15 (A) 一定存在互斥关系(B) 一定存在同步关系(C) 一定彼此独立无关(D) 可能存在同步或互斥关系参考答案：ABBCD第三十一次一、是非判断题（每小题1分，共10分）( 判断下列各题是否正确，如正确，在客观答题纸上对应编号选A，否则选B )1. 数据在计算机内存中的表示是指数据的存储结构。