软件技术基础总复习题及参考答案.doc

一、 选择题 软件技术基础 总复习题及参考答案1、 线性表若是采用链式存储结构时，要求内存中可用存储单元的地址 D 。 A、必须是连续的B、部分地址必须是连续的 C、一定是不连续的D、连续或不连续都可以 2、 栈和队列都是 B。 A、顺序存贮的线性结构B、限制存取点的线性结构 C、链接存贮的线性结构D、限制存取点的非线性结构 3、 与线性表的链接存贮不相符合的特性是 C。 A、便于插、删运算B、存贮空间动态分配 C、需要连续的存贮空间 D、只能顺序查找 4、 设二叉树的根为第一层，则第 i 层上的结点数最多有 B 。 ii A、B、+1 C、i -D、i -1 5、 如将一棵有 n 个结点的完全二叉树按顺序存放方式，存放在下标编号为 0, 1, n-1 的一维数组中，设某结点下标为 k(k0)，则其双亲结点的下标是 A 。 A、(k-1)/2 B、(k+1)/2C、k/2 D、k-1 6、 由权值分别为 3,8,6,2,5 的叶子结点生成一棵霍夫曼树，它的带权路径长度为 A 。 A、53B、48C、72D、24 7、 设 I 和 O 分别表示入栈和出栈操作，栈的初态和终态都为空，则下列操作序列 合法的有_ D_ _。 A、IOIOOIOI B、IOOIOIIO C、IIIOIOIOO D、IIOIIOOO 8、 二叉树的前序序列为 EFHIGJK，中序序列为 HFIEJKG，则二叉树的根为 C。 A、KB、G C、ED、H 9、 对有序表 -1, 0, 1, 3, 4, 6, 8, 10, 12 进行折半查找，则查找 12 需要 比较的次数为 B。 A、3B、4 C、5D、6 10、 在一个单链表中，若 q 结点是 p 结点的前驱结点，若在 q 与 p 之间插入结点 s， 则执行 D。 A、slink = plink; plink = s; B、plink = s; slink = q; C、plink = slink; slink = p; D、qlink = s; slink = p; 11、 一个栈的入栈序列为 a，b，c，则出栈序列不可能的是 C 。 A、c,b,a B、b,a,cC、c,a,b D、a,c,b 12、 如果将一棵有 n 个结点的完全二叉树按层次遍历次序，存放在下标编号为 0, 1, , n-1 的一维数组中，设某结点下标为 k( k 0 )，如果其左孩子存在， 则其左孩子结点的下标是 C。 A、2k 1 B、2k C、2k + 1 D、2k + 2 13、 用整数 5, 7, 3, 6, 4 作为五个树叶的权值，可以构造一棵带权路径长度值为 C的霍夫曼树。 A、78 B、62 C、57 D、25 14、 设单链表中结点结构为(data,link)，若想删除结点*p 的直接后继，则应执行 下列哪一个操作 A 。 A、p-link=p-link-link; B、p=p-link; p-link=p-link-link; C、p-link=p-link; D、p=p-link-link; 15、 顺序表是线性表的 B 。 A、链式存储结构 B、顺序存储结构 C、索引存储结构 D、散列存储结构 16、 若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前趋元素，则采用 A 存储方式最节省时间。 A、顺序表 B、单链表 C、双链表 D、单循环链表 17、 当利用大小为 n 的数组顺序存储一个栈时，假定用 top= =n 表示栈空，则向这 个栈插入一个元素时，首先应执行 B 语句修改 top 指针。 A、top+;B、top-; C、top=0;D、top; 18、 对于任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的结点为 n2.,则 A A、n0= n2+1 B、n2= n0+1 C、n0= 2n2+1 D、n2=2n0+1 19、 具有 35 个结点的完全二叉树的深度为 A 。 A、5 B、6 C、7 D、8 20、 在有向图中，所有顶点的入度之和是所有顶点出度之和的 B 倍。 A、0.5 B、1 C、2 D、4 21、 若用冒泡排序法对序列（18，14，6，27，8，12，16，52，10，26，47，29，41，24）从小到大进行排序，共要进行 B 次比较。 A、33 B、45 C、70 D、91 22、 对含有 B 个结点的非空二叉树，采用任何一种遍历方式，其结点访问序 列均相同。 A、0 B、1 C、2 D、不存在这样的二叉树 23、 数据结构是一门研究非数值计算的程序设计问题中计算机的 A以及它 们之间的 B和运算等的学科。A.数据元素B.计算方法C.逻辑存储D.数据映像A.结构B.关系C.运算D.算法 24、 数据结构在计算机内存中的表示是指 A。A.数据的存储结构B.数据结构 C.数据的逻辑结构D.数据元素之间的关系25、 在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C。 A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法26、 在数据结构中，从逻辑上可以把数据结构分成 C 。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 27、 带头结点的单链表 head 为空的判定条件是 B 。 A. head= =NULL B. head-next= =NULL C. head-next= =head D. head ! NULL 28、 在循环双链表的 p 所指结点之前插入 s 所指结点的操作是 D 。 A. p-prior=s；s-next=p；p-priornext=s；s-prior=p-prior； B. p-prior=s；p-prior-next=s；s-next=p；s-prior=p-prior； C .s-next=p；s-prior=p-prior；p-prior=s；p-right-next=s； D. s-next=p；s-prior=p-prior；p-priornext=s；p-prior=s； 29、 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表 B.静态链表 C.线性链表 D.顺序存储结构 30、 栈和队列的共同点是 C 。 A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有共同点 31、 向一个栈顶指针为 hs 的链栈中插入一个 s 所指结点时，则执行 C 。 A. hs-next=s; B. s-next=hs-next; hs-next=s; C. s-next=hs; hs=s; D. s-next=hs; hs=hs-next; 32、 判定一个环形队列 qu（最多元素为 MaxSize ）为空的条件是 C 。 A. qu-rear-qu-front= =MaxSize B. qu-rear-qu-front-l=MaxSize C. qu-front= =qu-rear D. qu-front= =qu-rear+l 33、 若用一个大小为 6 的一维数组来实现环形队列，且当前 rear 和 front 的值分 别为 0 和 3。当从队列中删除一个元素，再加入两个元素后，rear 和 front 的 值分别是 B 。 A. 1 和 5 B. 2 和 4 C. 4 和 2 D. 5 和 1 34、 在一个链队中，假设 f 和 r 分别为队头和队尾指针，则删除一个结点的运算是 C。 A. r=f-next; B. r=r-next; C. f=f-next; D. f=rnext; 35、 下图所示二叉树的中序遍历序列是 B 。 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 36、 深度为 5 的二叉树至多有 C 个结点。 A. 16B. 32C. 31D.1037、 对一个满二叉树，m 个树叶，n 个结点，深度为 h，则 D 。 A. n=h+mB. h+m=2nC. m=h-1D. n=2h-138、 下列说法正确的是 A。 A、链栈没有容量限制 B、顺序栈没有容量限制 C、链队有容量限制 D、单向链表有容量限制 39、 在一个无向图中，所有顶点的度数之和等于所有边数的 C倍。 A. 1/2B. 1C. 2D. 440、 对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是D。A. nB. (n-1)2C. n-1D. n241、 已知一个图如下图所示，若从顶点 a 出发按深度搜索法进行遍历，则可能得到 的一种顶点序列为 D；按广度搜索法进行遍历，则可能得到的一 种顶点序列为 B。A.a，b，e，c, d，fB. a，c，f，e，b，dC.a，e，b，c，f，dD. a，e，d，f，c，bA.a，b，c，e，d，fB. a，b，c，e，f，dC.a，e，b，c，f，dD. a，c，f, d，e，b42、 顺序查找法适合于存储结构为 B 的线性表。 A.散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储 43、 采用折半查找法查找长度为 n 的线性表时，每个元素的平均查找长度为 D 。 A.O(n2) B.O(nlog2 n) C.O(n) D. O(log2n) 44、 对有 18 个元素的有序表作折半查找，则查找 A3 的比较序列的下标为 D 。 A. 1、2、3 B.9, 5、2、3 C.9、5、3 D.9, 4、2、3 45、 有一数列 2、3、4、5，按 2、3、4、5 顺序入队，出队的顺序是 A。 A. 2345 B. 3245 C. 5342 D. 2435 46、 在排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空） 中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 C 。 A.希尔排序 B.冒泡排序 C.插入排序 D.选择排序 47、 在下列算法中， C 算法可能出现下列情况：在最后一趟开始之前，所 有的元素都不在其最终的位置上。 A.堆排序 B.冒泡排序 C.插入排序 D.快速排序 48、 在对 n 个元素进行冒泡排序的过程中，最好情况下的时间复杂度为 D 。 A. O(1) B.O (log2n) C. O(n2) D. O(n) 49、 在决定选取何种存储结构时，一般不考虑 A 。 A.各结点的值如何 B.结点个数的多少 C.对数据有哪些运算 D.所用编程语言实现这种结构是否方便 50、 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 B 。 A.数据元素具有同一特点 B.不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C.每个数据元素都一样 D.数据元素所包含的数据项的个数要相等 51、 不带头结点的单链表 head 为空的判定条件是 A 。 A. head= =NULL B. head-next= =NULL C. head-nexthead D. head != NULL 52、 非空的循环单链表 head 的尾结点（由 p 所指向）满足 C 。 A. p-next= =NULL B. p= =NULL C.p -next= =head D. p= =head 53、 某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用 D 存储方式最节省运算时间。 A.单链表 B仅有头结点的单循环链表 C.双链表 D.仅有尾指针的单循环链表 54、 如果最常用的操作是取第 i 个结点及其前驱，则采用 D 存储方式最节省 时间。 A.单链表 B.双链表 C.单循环链表 D.顺序表 55、 设线性表有 n 个元素，以下算法中， A 在顺序表上实现比在链表上实 现效率更高。 A. 输出第 i (0=inext=s；f=s; B. r-next=s；r=s; C. s-next=r；r=s; D. s-next=f；f=s; 62、按照二叉树的定义，具有 3 个结点的二叉树有 C 种。 A. 3 B. 4 C. 5 D. 6 63、任何一 棵二叉树的叶子结点在先序、 中序和后序遍历序列中的相对次序 A 。 A.不发生改变 B.发生改变 C.不能确定 D.以上都不对 64、一个有 n 个顶点的无向图最多有 C 条边。 A. n B. n(n-1) C.n(n-1)/2 D. 2n 65、在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要 C 条边。 A. n B. n+l C. n-1 D. n/2 66、对某个无向图的邻接矩阵来说， A 。 A第 i 行上的非零元素个数和第 i 列的非零元素个数一定相等 B.矩阵中的非零元素个数等于图中的边数 C.第 i 行上，第 i 列上非零元素总数等于顶点 Vi 的度数 D.矩阵中非全零行的行数等于图中的顶点数 67、采用邻接表存储的图的深度优先遍历算法类似于二叉树的 A 。 A.先序遍历 B.中序遍历 C.后序遍历 D.按层遍历 68、采用顺序查找法查找长度为 n 的线性表时，每个元素的平均查找长度为 C 。 A.n B.n/2 C.(n+1)/2 D.(n-1)/2 69、有一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当折半查找值 82 的结点时， C 次比较后查找成功。 A. 1 B. 2 C. 4 D. 8 70、在待排序的元素序列基本有序的前提下，效率最高的排序方法是 A 。 A.插入排序 B.选择排序 C.快速排序 D.归并排序 71、排序方法中，从未排序序列中挑选元素，并将其依次放入己排序序列（初始时为空）的一端的方法，称为 D 。 A.希尔排序 B.归并排序 C.直接插入排序 D.直接选择排序 72、下面程序段的时间复杂度为 A 。 m=0; for(i=1;i=n;i+) for(j=2*i;jnext= p-next; B. p= p-next-next； C. p-next= p-next-next； D. p= p-next; p-next= p-next-next； 80、在一非空二叉树的中序遍历序列中，根结点的右边 A 。 A 只有右子树上的所有结点 只有右子树上的部分结点 只有左子树上的部分结点 只有左子树上的所有结点 81、在一个图中，所有顶点的度数之和等于所有边数的 C 倍。 A1/2 1 2 4 82、从逻辑上可以把数据结构分为 C 两大类。 A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构 83、下面关于线性表的叙述中，错误的是 B 。 A线性表采用顺序存储，必须占用一片连续的存储单元 B线性表采用顺序存储，便于进行插入和删除操作 C线性表采用链接存储，不必占用一片连续的存储单元 D线性表采用链接存储，便于插入和删除操作 84、有关二叉树下列说法正确的是 B 。 A二叉树的度为 2 B一棵二叉树的度可以小于 2 C二叉树中至少有一个结点的度为 2 D二叉树中任何一个结点的度都为 2 85、下列说法不正确的是 C 。 A图的遍历是从给定的源点出发每一个顶点仅被访问一次 B遍历的基本算法有两种：深度遍历和广度遍历 C图的深度遍历不适用于有向图 D图的深度遍历是一个递归过程 86、利用二叉链表存储树，则根结点的右指针是 C 。 A指向最左孩子 B指向最右孩子 C空 D非空 87、下面关于二分查找的叙述正确的是 D 。 A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储 88、以下 B 不是队列的基本运算。 A从队尾插入一个新元素 B. 从队列中删除第 i 个元素 C. 判断一个队列是否为空 D. 读取队头元素的值 89、在长度为 n 的顺序表的第 i 个位置上插入一个元素（1 i n+1），元素的移 动次数为 A 。 A. n i + 1 B. n i C. i D. i 1 90、将一棵有 100 个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为 1，则编号最大的非叶结点的编号为 C 。 A. 48 B. 49C. 50D. 51 91、某二叉树结点的中序序列为 A、B、C、D、E、F、G，后序序列为 B、D、C、A、F、G、E，则其左子树中结点数目为 C 。 A3 B. 2 C. 4 D. 5 92、栈和队列都是 B 。 A、顺序存储的线性结构B、限制存取点的线性结构 C、链式存储的线性结构D、限制存取点的非线性结构93、用顺序查找方法查找长度为 n 的线性表时，在等概率情况下的平均查找长度为 D 。 A、nB、n/2C、(n-1)/2D、(n+1)/2 94、下列有关线性表的叙述中，正确的是 A。A、一个线性表是 n 个数据元素的有限序列 B、线性表中任何一个元素有且仅有一个直接前驱 C、线性表中任何一个元素有且仅有一个直接后继 D、以上说法都不正确95、对线性表进行二分查找时，要求线性表必须 C。A、以顺序方式存储 B、以链接方式存储 C、以顺序方式存储，且数据元素有序D、以链接方式存储，且数据方式有序 96、一个队列的入列序列是，则队列的输出序列是 B。A、4,3,2,1 B、1,2,3,4 C、1,4,3,2 D、3,2,1,497、从一个长度为 n 的顺序表中删除第 i 个元素(1in)时,需向前移动 A 个元素。A、n-iB、n-i+1C、n-i-1D、i98、按照二叉树的定义，具有 3 个结点的二叉树有 A种。 A、3B、4C、5D、699、一个栈的入栈序列是 a,b,c,d,e,则栈的不可能的输出序列是 C。 A、edcbaB、decbaC、dceabD、abcde100、采用线性链表表示一个向量时，要求占用的存储空间地址 D。A必须是连续的B部分地址必须是连续的C一定是不连续的D可连续可不连续101、在一个单链表中，若 q 结点是 p 结点的前驱结点，若在 q 与 p 之间插入结点 s， 则执行 D。A snext = pnext;pnext = s;B pnext = s;snext = q;C pnext = snext;snext = p;D qnext = s;snext = p;102、下面程序段的时间复杂度为 C。for (int i=0;im;i+)for (int j=0;jn;j+) aij=i*j;AO(m2)B O(n2)CO(m*n)DO(m+n)103、数据结构的定义为(D，S)，其中 D 是 B的集合。A算法B 数据元素C数据操作D 逻辑结构104、栈的数组表示中，top 为栈顶指针，栈空的条件是 A。Atop=0Btop=maxSizeC top=maxSizeD top=-1105、下面 B 的时间复杂性最好，即执行时间最短。 A. O(n)B.O(logn)C.O(nlogn)D.O(n2) 106、深度为 k 的完全二叉树至多有 A个结点。A.2k-1B.2k-2C.2k-1D.2k-2107、对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序，当 把第 7 个记录 60 插入到有序表时，为寻找插入位置需比较 C次。A.1B.2C.3D.4108、折半查找有序表（6，15，30，37，65，68，70，72，89，99），若查找元素 37， 需依次与表中元素 D进行比较。A.65，15，37B.68，30，37C.65，15，30D.65，15，30，37109、如图所示的 4 棵二叉树中， A不是完全二叉树。（A）(B)(C)(D)110、计算机算法指的是 C。A. 计算方法B. 排序方法C.解决问题的有序序列D. 调度方法111、关系数据库是用 D 实现数据之间的联系的。 A. 关系 B.指针 C.表 D.公共属性 112、逻辑模型独立于 B 。 A. E-R 模型 B.硬件设备 C. DBMS D.操作系统和 DBMS、 113、鉴定用户身份、设置口令、控制用户存取权限、数据加密等是 A 采取的措施。 A.数据安全性控制 B.数据完整性控制 C.故障恢复 D.并发控制 114、数据库应用系统的核心是 B 。 A.数据库文件 B.数据库管理系统 A. 编辑程序 D.操作系统 115、在数据管理技术发展过程中，文件系统与数据库系统的重要区别是数据库系统 具有 C 。 A.数据可共享 B.数据无冗余 C.特定的数据模型 D.专门的数据管理软件 116、关系数据库的数据操作语言(DML)主要包括 D 两类操作。 A. 删除和插入B. 查询和检索 C. 统计和修改D. 检索和更新 117、数据库的三级体系结构是对 C 抽象的 3 个级别。 A存储器B. 数据库系统 C. 数据D. 数据库管理系统 118、数据库是按一定的规则存储在计算机中的相关数据的集合，能被各种用户共享。数据库管理系统是 C 。 A. 采用了数据库技术的计算机系统 B. 包括数据库管理人员、计算机软硬件以及数据库的系统 C. 位于用户与操作系统之间的一层数据管理软件 D. 包含操作系统在内的数据管理软件系统 119、五种基本关系代数运算是 C 。 A. 并、差、笛卡尔积、投影、联接 B. 并、差、笛卡尔积、选择、联接 C. 并、差、笛卡尔积、投影、选择 D. 并、差、笛卡尔积、除法、投影 120、数据库管理系统通常提供授权功能来控制不同用户访问数据的权限，这主要是 为了实现数据库的 D 。 A. 可靠性 B. 一致性 C. 完整性 D. 安全性 121、数据的完整性为 D 。 A. 数据的可靠性 B. 数据的独立性、可能性 C. 数据的一致性 D. 数据的正确性和相容性 122、数据模型的三要素包括数据结构、数据操作和 D 。 A. 联系 B. 正确性C. 一致性D. 完整性约束。 123、在数据库设计过程中，画 ER 图是在 B 阶段完成的。 A. 需求分析 B. 概念结构设计 C. 逻辑结构设计D. 数据库物理设计 124、下列叙述正确的为 D 。 A. 主码是一个属性，它能唯一表识一列 B. 主码是一个属性，它能唯一表识一行 C. 主码是一个属性或属性集，它能唯一表识一列 D. 主码是一个属性或属性集，它能唯一表识一行 125、有关系 R 和 S，RS 的运算等价于 B 。 A. S-(R-S) B. R-(R-S) C. (R-S)S D. R(R-S) 126、要保证数据库逻辑数据独立性，需要修改的是 C 。 A. 模式B. 模式与内模式的映射 C. 模式与外模式的映射D. 内模式 127、下列四项中，不属于数据库特点的是 C 。 A. 数据共享B. 数据完整性 C. 数据冗余很高D. 数据独立性高 128、学生社团可以接纳多名学生参加，但每个学生只能参加一个社团，从社团到学 生之间的联系类型是 D 。 A. 多对多B. 一对一 C. 多对一D. 一对多 129、反映现实世界中实体及实体间联系的信息模型是 D 。 A. 关系模型B. 层次模型 C. 网状模型D. E-R 模型 130、对数据库并发操作有可能带来的问题包括 A 。 A. 读出“脏数据”B. 带来数据的冗余 C. 未被授权的用户非法存取数据D. 破坏数据独立性 131、关系数据模型的三个组成部分中，不包括 D 。 A. 完整性规则B. 数据结构 C. 数据操作D. 并发控制 132、SQL 中，“DELETE FROM 表名”表示 A 。 A、从基本表中删除所有元组B、从基本表中删除所有属性 C、从数据库中撤消这个基本表 D、从基本表中删除重复元组 133、公司中有多个部门和多名职员，每个职员只能属于一个部门，一个部门可以 有多名职员，从职员到部门的联系类型是 D 。 A、多对多 B、一对一 C、多对一 D、一对多 134、关系笛卡尔积运算记号 RS， D 。 A、R 为关系名，S 为属性名B、R 和 S 均为属性名 C、R 为属性名，S 为关系名D、R 和 S 均为关系名 135、如果有 9 个不同的实体集，它们之间存在着 12 个不同的二元联系（二元联 系是指两个实体集之间的联系），其中 4 个 1:1 联系，4 个 1:N 联系，4 个 M:N联系，那么根据 ER 模型转换成关系模型的规则，这个 ER 结构转换成的关系模 式个数至少为 B 。 A、9 个 B、13 个 C、17 个 D、21 个 136、SQL 中，聚合函数 COUNT（列名）用于C。 A、计算元组个数B、计算属性的个数 C、对一列中的非空值计算个数D、对一列中的非空值和空值计算个数 137、SQL 语言通常称为 A 。 A. 结构化查询语言B. 结构化控制语言 C. 结构化定义语言D. 结构化操纵语言 138、SQL 中，下列涉及空值的操作，不正确的是 C 。 AAGE IS NULL BAGE IS NOT NULL CAGE=NULL DNOT (AGE IS NULL) 139、一个 1 ： n 联系可以转换为一个独立的关系模式，关系的码为 C