计算机软件技术基础复习题答案

计算机软件技术基础复习题答案内容摘要：

DBBC ，插入到链表，或从链表删除一个整数。 阅读下面的 C 代码，将应填入 (n) 处的字名写在答卷的对应栏内。 include include typedef struct node{ int val。 struct node * next。 }NODE。 NODE * ins(NODE *list, int x){ /*将 x 按从小到大的次序插入链表 */ NODE *u, *v=list, *p。 for(。 v != NULL amp。 amp。 x vval。 v = vnext)。 /*寻找插入位置 */ if(v != NULL amp。 amp。 x == vval) return(list)。 /*已有，被忽略 */ p = (NODE *)malloc(sizeof(NODE))。 pval=x。 /*生成新表元 */ if(v == list) list = p。 else (1)。 (2)。 return list。 } NODE * del(NODE * list, int x){ /*从链表中删除值为 x 的表元 */ NODE *u, *v。 for(v = list。 v != NULL amp。 amp。 x vvalu。 u=v。 v=vnext)。 if(v != NULL amp。 amp。 x == vval){ /*找到值为 x 的表元 */ if(v == list) list = listnext。 else (3)。 (4)。 /*释放空间 */ } else printf(“ 没有找到 !\n” )。 return(list)。 } main(){ int x,ans。 NODE * list=NULL, *p。 while(1){ printf(“ \n 输入 1：将整数插入到链表。 \n 输入 2：从链表删除一个整数。 \n” )。 printf(“ 其它整数，结束程序。 \n\t 请输入选择。 ” )。 scanf(%d,amp。 ans)。 if( (5) ) return。 printf(“ 输入整数： ” )。 scanf(“ %d” ,amp。 x)。 if(ans==1) list=ins(list,x)。 else list=del(list,x)。 for(p=list。 p!=NULL。 p=pnext) printf(“ %4d” ,pval)。 } } 答案： (1) unext = p。 (2) pnext = v (3) unext = vnext (4) free(v) (5) ans != 1 amp。 amp。 ans != 2 46. 从未排序的序列中，依次取出元素，与已排序序列的元素比较后，放入已排序序列中的恰当位置上，这是 (1) 排序。 从未排序的序列中，挑选出元素，放在已排序序列的某一端位置，这是 (2) 排序。 逐次将待排序的序列中的相邻元素两两比较，凡是逆序则进行交换，这是 (3) 排序。 如果整个排序过程都在内存中进行，称为 (4) 排序。 排序算法的复杂性与 排序算法的 (5) 有关。 供选答案： (1): A. 选择 B. 插入 C. 比较 D. 归并 (2): A. 选择 B. 插入 C. 比较 D. 归并 (3): A. 冒泡 B. 交换 C. 比较 D. 散列 (4): A. 外部 B. 内部 C. 外存 D. 内存 (5): A. 运算量大小与占用存储多少 B. 运算量大小与处理的数据量大小 C. 并行处理能力和占用存储多少 D. 占用存储多少和处理的数据量大小 答案： BAABA (1) 系统软件，是 (2) 的接口。 在处理机管理中，进程是一个重要的概念，它由程序块、 (3) 和数据块三部分组成，它有 3 种基本状态，不可能发生的状态转换是 (4)。 虚拟存储器的作用是允许程序直接访问比内存更大的地址空间，它通常使用 (5) 作为它的一个主要组成部分。 供选答案： (1): A. 输入和输出 B. 键盘 操作 C. 管理和控制 D. 汇编和执行 (2): A. 软件和硬件 B. 主机和外设 C. 高级语言和机器语言 D. 用户和计算机 (3): A. 进程控制块 B. 作业控制块 C. 文件控制块 D. 设备控制块 (4): A. 运行态转换为就绪态 B. 就绪态转换为运行态 C. 运行态转换为等待态 D. 等待态转换为运行态 (5): A. 软盘 B. 硬盘 C. CDROM D. 寄存器 答案： CDADB 48. A 是信息的载体，它能够被计算机识别、存储和加工处理。 A. 数据 B. 数据元素 C. 结点 D. 数据项 C。 for(i=1。 in。 i++){ y=y+1。 for(j=0。 j=(2*n)。 j++) x++。 } 供选答案： A. O(n1) B. O(2n) C. O(n2) D. O(2n+1) D。 i=1。 while(i=n) i=i*2。 供选答案： A. O(1) B. O(n) C. O(n2) D. O(log2n) B。 a=0。 b=1。 for(i=2。 i=n。 i++){ s=a+b。 b=a。 a=s。 } 供选答案： A. O(1) B. O(n) C. O(log2n) D. O(n2) ，计算机的 A 以及它们之间的关系和运算等的学科。 B. 计算方法 C. 逻 辑存储 D. 数据映象 ，从逻辑上可以把数据结构分成 C。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构 C。 A. 找出数据结构的合理性 B. 研究算法中输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 (4)。 A. 间复杂性和时间复杂性 B. 正确性和简明 性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 100，每个元素的长度为 2，则第 5 个元素的地址为 B。 A. 110 B. 108 C. 100 D. 120 1,2,3,„ ,n，其输出序列为 P1,P2,P3,„ ,Pn，若 P1=n，则 Pi为 C。 A. i B. ni C. ni+1 ，给出输入项 A,B,C。 如果输 入项序列由 A,B,C 所组成，则不可能产生的输出序列是 A。 A. CAB B. CBA C. ABC D. ACB ，其时间复杂度为 B。 LinkNode *GetNode(Linklist head, int i){ int j。 ListNode *p。 P = head。 j=0。 while(pnext amp。 amp。 ji){ p = pnext。 j++。 } if(i==j) return(p)。 else return(NULL)。 } 供选答案： A. O(n2) B. O(2n) C. O(n3) D. O(logn) Amn按行序为主顺序存放在内存中，每个数组元素占 1 个存储单元，则元素 aij的地址计算公式是 C。 A. LOC(aij) = LOC(a11)+[(i1)*m+(j1)] B. LOC(aij) = LOC(a11)+[(j1)*m+(i1)] C. LOC(aij) = LOC(a11)+[(i1)*n+(j1)] D. LOC(aij) = LOC(a11)+[(j1)*n+(i1)] C。 A. 从队尾插入一个新元素 B. 从队列中删除第 i 个元素 C. 判断一个队列是否为空 D. 读取队头元素的值 n 的顺序表中，向第 i 个元素之前插入一个新元素，需向后移动 B 个元素。 A. ni B. ni+1 C. ni1 D. i n 的顺序表中删除第 i 个元素时， 需向前移动 A 个元素。 A. ni B. ni+1 C. ni1 D. i n 个单元的顺序存储的循环队列中，假定 front和 rear 分别为队首指针和队尾指针，则判断队空的条件是 B。 A. front=rear+1 B. front=rear C. front+1=rear D. front=0 n 个结点的单链表中查找其值等于 x 的结点时，在查找成功的情况下，需平均比较 D 个结点。 A. n B. n/2 C. (n1)/2 D. (n+1)/2 a,b,c,d,e，则栈不可能的输出序列是 C。 A. edcba B. decba C. dceab D. abcde A。 A. 顺序存储结构和链表存储结构 B. 散列方式和索引方式 C. 链表存储结构和数组 D. 线性存储结构和非线性存储结构 ST（最多元素为 mo）为空的条件是 B。 A. STtop0 B. STtop=0 C. sttopmo D. sttop==mo head 为空表的判定条件是 A。 A. head==NILL B. headnext==NULL C. headnext==head D. head != NULL ，已知 q 所指结点是 p 所指结点的前驱结点，若在 p和 q 之间插入 s 结点，则应执行 C。 A. snext = pnext。 pnext=s。 B. pnext = snext。 snext=p。 C. qnext = s。 snext=p。 D. pnext = s。 snext=q。 ： typedef struct Linknode{ int data。 struct Linknode *lLink。 /*前驱结点指针 */ struct Linknode *rLink。 /*后继结点指针 */ } 下面给出的算法是要把一个 q 所指新结点，作 为非空双向链表中的 p 所指的结点前驱结点插入到该双向链表中，能正确完成要求的算法段是 C。 A． qrLink=p。 qlLink=plLink。 plLink=q。 plLinkrLink=q。 B. plLink=q, qrLink=p。 plLinkrLink=q。 qlLink=plLink。 C. qlLink=plLink。 qrLink=p。 plLinkrLink=q。 plLink=q。 D. 以上均不对 ，其特殊性体现在 B。 A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符 p 和 q，求 q 在 p 中首次出现的位置的运算称作 B。 A. 连接 B. 模式匹配 C. 求子串 D. 求串长 s1=” ABCDEFG” ， s2=” PQRST” ，函数 con(x,y)返回 x和 y串的连接串， subs(s,I,j)返回串 s 的从序号 i 的字符开始的 j 个字符组成的子串， len(s)返回串 s 的长度，则con(sub(s1,2,len(s2)),sub(s1,len(s2),2))的结果是 D。 A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF C。 A. 建立和删除 B. 索引和。