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

printf(“Enter Integers:\\n”);

while(scanf(“%d”,&x) == 1) /*反复读入整数插入链表*/ insert(head,x);

for(p=head->next;p!=NULL;p=p->next) /*输出链表*/ printf(“%d\\t”,p->val); printf(“\\n”); }

答案：

(1) v != NULL或v

(2) x > v->val 或 x != v->val (3) p->next (4) u->next (5) head->next

44.计算机数据处理的对象是具有不同结构的各种数据，可以访问的最小数据信息单位是 (1) ，可以引用的最小命名数据单位是 (2) 。

线性表是最简单的一种数据结构，有顺序和链接两种存储方式。线性表按链接方式存储时，每个结点的包括 (3) 两部分。

线性表的查找有 (4) 和 (5) 两种，但 (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. 浏览 答案：CDBBC

45.本程序用于从链盘读入整数，插入到链表，或从链表删除一个整数。

阅读下面的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 && x < v->val ; v = v->next);/*寻找插入位置*/ if(v != NULL && x == v->val) return(list); /*已有，被忽略*/

p = (NODE *)malloc(sizeof(NODE));p->val=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 && x < v->valu; u=v;v=v->next); if(v != NULL && x == v->val){ /*找到值为x的表元*/ if(v == list) list = list->next; 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,&ans);

if( (5) ) return;

printf(“输入整数：”);scanf(“%d”,&x); if(ans==1) list=ins(list,x); else list=del(list,x); for(p=list;p!=NULL;p=p->next) printf(“M”,p->val); } }

答案：

(1) u->next = p; (2) p->next = v

(3) u->next = v->next (4) free(v)

(5) ans != 1 && 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

47.操作系统是对计算机资源进行的 (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. 数据项 49.下列程序段的时间复杂度为 C 。 for(i=1;i

for(j=0;j<=(2*n);j++) x++; }

供选答案：

2

A. O(n-1) B. O(2n) C. O(n) D. O(2n+1) 50.下面程序段的时间复杂度为 D 。 i=1;

while(i<=n) i=i*2; 供选答案：

A. O(1) B. O(n) C. O(n2) D. O(log2n) 51.下面程序段的时间复杂度为 B 。 a=0;b=1;

for(i=2;i<=n;i++){ s=a+b; b=a;

a=s; }

供选答案：

2

A. O(1) B. O(n) C. O(log2n) D. O(n)

52.数据结构是一门研究非数值计算的程序设计问题中，计算机的 A 以及它们之间的关系和运算等的学科。

A.操作对象 B. 计算方法 C. 逻辑存储 D. 数据映象 53.在数据结构中，从逻辑上可以把数据结构分成 C 。

A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构 54.算法分析的目的是 C 。 A. 找出数据结构的合理性

B. 研究算法中输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性

55.算法分析的两个主要方面是 (4) 。

A. 间复杂性和时间复杂性 B. 正确性和简明性

C. 可读性和文档性 D. 数据复杂性和程序复杂性 56.一个线性顺序表第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址为 B 。

A. 110 B. 108 C. 100 D. 120

57.若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为P1,P2,P3,…,Pn，若P1=n，则Pi为 C 。

A. i B. n-i C. n-i+1 D.不确定

58.对于一个栈，给出输入项A,B,C。如果输入项序列由A,B,C所组成，则不可能产生的输出序列是 A 。

A. CAB B. CBA C. ABC D. ACB 59.设有如下的单链表的按序号查找的算法，其时间复杂度为 B 。 LinkNode *GetNode(Linklist head, int i){ int j;

ListNode *p; P = head; j=0;

while(p->next && j

p = p->next; j++; }

}

供选答案：

23

A. O(n) B. O(2n) C. O(n) D. O(logn)

60.二维数组Amn按行序为主顺序存放在内存中，每个数组元素占1个存储单元，则元素aij的地址计算公式是 C 。

A. LOC(aij) = LOC(a11)+[(i-1)*m+(j-1)] B. LOC(aij) = LOC(a11)+[(j-1)*m+(i-1)] C. LOC(aij) = LOC(a11)+[(i-1)*n+(j-1)] D. LOC(aij) = LOC(a11)+[(j-1)*n+(i-1)]

61.以下哪一个不是队列的基本运算 C 。

A. 从队尾插入一个新元素 B. 从队列中删除第i个元素 C. 判断一个队列是否为空 D. 读取队头元素的值 62.在一个长度为n的顺序表中，向第i个元素之前插入一个新元素，需向后移动 B 个元素。

A. n-i B. n-i+1 C. n-i-1 D. i

63.从一个长度为n的顺序表中删除第i个元素时，需向前移动 A 个元素。 A. n-i B. n-i+1 C. n-i-1 D. i 64.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是 B 。

A. front=rear+1 B. front=rear C. front+1=rear D. front=0

65.从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较 D 个结点。

A. n B. n/2 C. (n-1)/2 D. (n+1)/2 66.一个栈的入栈序列是a,b,c,d,e，则栈不可能的输出序列是 C 。 A. edcba B. decba C. dceab D. abcde 67.栈结构通常采用的两种存储结构是 A 。

A. 顺序存储结构和链表存储结构 B. 散列方式和索引方式

C. 链表存储结构和数组 D. 线性存储结构和非线性存储结构 68.判断一个顺序栈ST（最多元素为mo）为空的条件是 B 。

A. ST->top<>0 B. ST->top=0 C. st->top<>mo D. st->top==mo 69.不带头结点的单链表head为空表的判定条件是 A 。

A. head==NILL B. head->next==NULL C. head->next==head D. head != NULL 70.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p和q之间插入s结点，则应执行 C 。

A. s->next = p->next; p->next=s; B. p->next = s->next; s->next=p; C. q->next = s; s->next=p; D. p->next = s; s->next=q;

71.假设双向链表结点的类型如下： typedef struct Linknode{

if(i==j)

return(p); else

return(NULL);