第1页 / 共37页
第2页 / 共37页
第3页 / 共37页
第4页 / 共37页
第5页 / 共37页
第6页 / 共37页
第7页 / 共37页
第8页 / 共37页
《计算机软件技术基础》复习题及答案(完美打印版).doc
《计算机软件技术基础》试题
CD
。
的有限序列。
C
B. 字符
B. 便于随机存取
D. 便于利用零散的存储器空间
1.线性表的链式存储结构与顺序存储结构相比优点是
A. 所有的操作算法实现简单
C. 便于插入和删除
2.线性表是具有 n 个
A. 表元素
D. 数据项
3.若长度为 n 的线性表采用顺序存储结构，在其第 I 个位置插入一个新元素的算法的时间复
杂度为
A. O(0)
C. O(n)
4.设 A 是一个线性表(a1,a2,…,an)，采用顺序存储结构，则在等概率的前提下，平均每插入
一个元素需要移动的元素个数为
，平均每删除一个元素需要移动的元素个数为
C. 数据元素
E. 信息项
B. O(1)
D. O(n2)
。（1≤I≤n+1）
B
C
A
；若元素插在 ai 与 ai+1 之间(0≤I≤n-1)的概率为
(2
(
nn
)
in
)1
，则平均每插入一个
元素所要移动的元素个数为
C
；
A.
C.
1n
2
2 n
3
1
B.
D.
n
2
3 n
4
1
n
5.下列函数中，按它们在
A. logn
C. 2n/2
6.将下图所示的 s 所指结点加到 p 所指的结点之后，其语句应为：
时的无穷大阶数，最大的是
B. nlogn
D. n!
D
。
D
。
next
next
p
s
next
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. n
C. n-1
8.下面的程序段是合并两个无头结点链表(ha 和 hb)为一个无头结点链表 ha 的过程，作为
参数的两个链表都是按结点的 data 域由大到小链接的。合并后新链表的结点仍按此方式链
接。请填写下述空框，使程序能正确运行。
B. 2n-1
D. 2n
。
A
#define NULL 0
1
typedef 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){
(1)
;
p->next =
p =
(2)
(3)
;
}
else{
p->next =
p =
(5)
(4)
;
(6)
;
}
if(ha==NULL)
if(hb==NULL)
ha = h->next;
free(h);
(7)
(8)
;
;
}
参考答案： (1) ha
(4) hb
(7) p->next=hb
(2) p->next
(5) p->next
(3) ha=ha->next
(6) hb=hb->next
(8) p->next=ha
9.如果表 A 中所有元素(a1,a2,…,an)与表 B 的一个顺序子表(bk,bk+1,…bk+n-1)完全相同（即
a1=bk,a2=bk+1,…an=bk+n-1），则称表 A 包含在表 B 中。设 ha，hb 为带头结点的单链表，分别表
示有序表 A 和 B，下面的函数用于判别表 A 是否包含在表 B 中，若是，则返回 true，否则返
回 false。（提示：用递归实现）
#define true 1
#define false 0
#define NULL 0
typedef struct node{
int data;
struct node *next;
}node, linklisttype;
int inclusion(linklisttype *ha, linklisttype *hb){
linklisttype *pa, *pb;
pa = ha->next;
pb = hb->next;
2
(1)
while(
;
(2)
)
if(pa->data=pb->data)
else
(5)
;
(3)
(4)
;
;
}
参考答案：
(1) if(pa==NULL) return(true)
(2) pb!=NULL && pa->data>=pb->data
(3) return(inclusion(pa, pb))
(4) pb = pb->next;
(5) return(false)
10.在本题的程序中，函数 create_link_list(n)建立一个具有 n 个结点的循环链表；函数
josephus(n,I,m)对由 create_link_list(n)所建立的具有 n 个结点的循环链表按一定的次
序逐个输出，并删除链表中的所有结点。参数 n(n>0)指明循环链表的结点个数，参数 I(1
≤I≤n)指明起始结点，参数 m（m>0 是步长），指明从起始结点或前次被删除并输出的结点
之后的第 m 个结点作为本次被输出并删除的结点。例如，对于下图所示的具有 6 个结点的循
环链表，在调用 josephus(6,3,2)后，将输出 5,1,3,6,4,2。请在空框处填上适当内容，每
框只填一个语句。
#define NULL 0
typedef struct node{
int data;
struct node *next;
}node, linklisttype;
linklisttype *create_link_list(int n){
linklisttype *head, *p, *q;
int I;
head = NULL;
if(n>0){
head = (linklisttype *)malloc(sizeof(linklisttype));
p = head;
for(I=1;I<=n-1;I++){
/*此循环用于建立一个链表，链表的内容从 1 至 n-1*/
p->data = I;
q = (linklisttype *)malloc(sizeof(linklistttype));
(1)
(2)
;
;
}
p->data = n;
(3)
;
/*建立从尾链到首的环形结构*/
}
return(head);
3
}
void Josephus(int n, int j, int m){
linklisttype *p, *q;
int j;
p = create_link_list(n);
for(;I>1;I--)
p = p->next;
(4)
;
while(jnext;
(5)
;
printf(“%8d”,q->data);
;
(6)
free(q);
j=j+1;
}
}
参考答案：
(1) p->next = q;
(2) p = q;
(3) p->next = head
(4) j=0
(5) q=p->next;
(6) p->next = q->next
11.在下列程序中，函数 difference(A,B)用于求两集合之差 C=A-B，即当且仅当 e 是 A 中的
一个元素，且不是 B 中的元素时，e 是 C 中的一个元素。集合用有序链表实现，用一个空链
表表示一个空集合，表示非空集合的链表根据元素之值按递增排列，执行 C=A-B 之后，表示
集合 A 和 B 的链表不变，若结果集合 C 非空，则表示它的链表应根据元素之值按递增序排列。
函数 append()用于在链表中添加结点。
#include
#define NULL 0
typedef struct node{
int data;
struct node *next;
}NODE;
NODE *append(NODE *last, int x){
last->next=(NODE *)malloc(sizeof(NODE));
last->next->data=x;
return(last->next);
}
NODE *difference(NODE *A ,NODE *B){
4
NODE *C,*last;
C=last=(NODE *)malloc(sizeof(NODE));
while(
(1)
)
if(A->data < B->data){
last=append(last,A->data);
A=A->next;
}
else
if(
(2)
){
A=A->next;
B=B->next;
}
else
(3)
;
while(
(4)
){
last=append(last,A->data);
A=A->next;
}
(5)
;
last=C;
C=C->next;
free(last);
return(C);
}
参考答案：
(1) A!=NULL & B!=NULL
(2) A->data==B->data
(3) B=B->next;
(4) A!=NULL
(5) last->next=NULL;
12.阅读以下算法，填充空格，使其成为完整的算法。其功能是在一个非递减的顺序存储线
性表中(从下标 1 处开始存储)，删除所有值相等的多余元素。
#define MAXSIZE 30
typedef struct{
int elem[MAXSIZE];
int length;/*表长*/
}sqlisttype;
void exam21(sqlisttype *L){
int i,j;
i=1,j=2;
while(
if(L->elem[i]!=L->elem[j])
{
(1)
){
5
if(j!=(i+1))
(2)
;
L->length=L->length-(j-i-1);
(3)
;
}
else
{
(4)
if(j>L->length)
}
;
(5)
;
}
}
参考答案：
(1) j<=L->length
(2) for(int k=j;k<=L->length;k++)
(3) i++,j=i+1;
(4) j++;
(5){L->length=L->length-(j-i-1);
L->elem[k-(j-i-1)]=L->elem[k];
break;}
B. 链尾
D
位置。
A
。
B
B
结构。
B. 队列
D. 线性表
B. 带尾指针的循环链表
D. 带头指针的循环链表
13.用单链表表示的链式队列的队头在链表的
A. 链头
C. 链中
14.若用单链表表示队列，则应该选用
A. 带尾指针的非循环链表
C. 带头指针的非循环链表
15.在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主
机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印，先放入打印
缓冲区的数据先被打印。该缓冲区应该是一个
A. 堆栈
C. 数组
16.若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别为 0 和 3。当
从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为
A. 1 和 5
C. 4 和 2
17.设栈的输入序列为 1,2，…,10，输出序列为 a1,a2,…,a10，若 a5=10，则 a7 为
A. 4
18.设栈的输入序列是 1,2,3,4，则
A． 1243
19.以下
A. abcd
20.若串 S=”software”，其子串的数目是
A. 8
21.将一个 A[1:100,1:100]的三对角矩阵，按行优先存入一维数组 B[1:298]中，A 中元素
A66,65(即该元素的下标)在 B 数组中位置 k 为
A. 198
不可能是其出栈序列。
D. 4312
是 C 语言中”abcd321ABCD”的子串。
C.不确定
D
C. 1432
B. 2 和 4
D. 5 和 1
C. “abcABC”
B. 195
C. 197
D. “21AB”
B. 37
C. 36
D. 9
B
。
B. 8
B. 2134
B. 321AB
C
。
B
。
C
。
D.7
D. 196
6
F
B
个结点。
F
E
，至多为
B
F
，
。
D.h+1
H. 2h+1
D. 251
B. 248
C. 249
B. 2h-1
F. 2h-1
C. 2h+1
G. 2h+1-1
。高为 h 的完全二叉树的结点数至少为
22.设高为 h 的二叉树只有度为 0 和 2 的结点，则此类二叉树的结点数至少为
至多为
A． 2h
E. 2h-1
23.一棵有 124 个叶结点的完全二叉树，最多有
A. 247
24.若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉
树是
C
A. 满二叉树
C. 堆
25.前序遍历和中序遍历结果相同的二叉树为
的二叉树为
A. 一般二叉树
C. 根结点无左孩子的二叉树
E. 所有结点只有左孩子的二叉树
26.具有 n 个结点的完全二叉树，已经顺序存储在一维数组 A[1..n]中，下面的算法是将 A
中顺序存储变为二叉链表存储的完全二叉树。请填写适当语句在下面的空格内，完成上述算
法。
#define MAXSIZE 30
typedef struct btnode{
B. 只有根结点的二叉树
D. 根结点无右孩子的二叉树
F. 所有结点只有右孩子的二叉树
B. 哈夫曼树
D. 二叉查找树
；前序遍历和后序遍历结果相同
。
B
。
int data;
struct btnode *lchild, *rchild;
}BTN;
void createtree(BTN *p,int A[], int I,int n){
(1)
;
p->data=A[I];
(2)
if(
(3)
else
)
;
p->lchild=NULL;
if(
(4)
)
createtree(
(5)
);
else
p->rchild=NULL;
}
void btree(BTN * p ,int A[],int n){
createtree(p,A,1,n);
}
参考答案：
(1) p=(BTN *)malloc(sizeof(BTN))
(2) 2*I<=n
(3) createtree(p->lchild,A,2*I,n)
(4) 2*I+1<=n
7
(5) p->rchild,A,2*I+1,n
27.若在线性表中采用折半查找法查找元素，该线性表应该
A. 元素按值有序
C. 元素按值有序，且采用顺序存储结构 D. 元素按值有序，且采用链式存储结构
28.在分块检索中，对 256 个元素的线性表分成
B. 采用顺序存储结构
。
C
16
；若每块的长度为 8，其平均检索长度为
块最好，每块的最佳长度是
21
。
16
D
次探测。
29.假定有 K 个关键字互为同义词，若用线性探测法把这 K 个关键字存入散列表中，至少要
进行
A. K-1 次
C. K+1 次
30.在 n 个记录的有序顺序表中进行折半查找，最大的比较次数是
B. K 次
D. K(K+1)/2 次
1
n
log 2
。
C
A
B
。
。
。
和
B. 归并排序
，平均速度最快的是
，所需辅助存储空间最小
31.Hash 技术广泛应用于查找过程，选择 Hash 函数的标准是
处理冲突的技术有优有劣，其共同标准是
32.在下述排序算法中，所需辅助存储空间最多的是
的是
C. 堆排序
A.快速排序
33.在文件局部有序或文件长度较小的情况下，最佳内部排序的方法是
A. 直接插入排序
34.快速排序在最坏情况下时间复杂度是 O(n2)，比
A. 堆排序
35.若需在 O(nlogn)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方
C
法是
A. 快速排序
C. 归并排序
36.如果只想得到 1000 个元素组成的序列中第 5 个最小元素之前的部分排序的序列，用
C. 简单选择排序
的性能差。
C. 简单选择排序
B. 堆排序
D. 希尔排序
B. 冒泡排序
B. 冒泡排序
。
。
A
A
B
方法最快。
A
。
E. 简单选择排序
B. 快速排序
D. 堆排序
A. 冒泡排序
C. 希尔排序
37.以下结点序列是堆的为
A. 100,90,80,60,85,75,20,25,10,70,65,50
B. 100,70,50,20,90,75,60,25,10,85,65,80
38.若要尽可能快地完成对实数数组的排序，且要求排序是稳定的，则应选
A. 快速排序
C. 归并排序
39.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在
已排序序列的合适位置，该排序方法称为
A. 插入排序
C. 选择排序
40.直接插入排序在最好情况下的时间复杂度为
A. O(logn)
C. O(nlogn)
41.下面函数是将任意序列调整为最大堆的算法，请将空白部分填上：
将任意序列调整为最大堆通过不断调用 adjust 函数，即
B. 交换排序
D. 归并排序
B. 堆排序
D. 希尔排序
B. O(n)
D. O(n2)
排序法。
。
。
C
A
B
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
