《计算机软件基础》复习题库带答案文档

《计算机软件基础》复习题库(带答案)

1.线性表的链式存储结构与顺序存储结构相比优点是 CD 。 A. 所有的操作算法实现简单 C. 便于插入和删除

B. 便于随机存取

D. 便于利用零散的存储器空间

2.线性表是具有n个 C 的有限序列。 A. 表元素 D. 数据项

B. 字符

C. 数据元素 E. 信息项

3.若长度为n的线性表采用顺序存储结构，在其第I个位置插入一个新元素的算法的时间复杂度为 C 。（1≤I≤n+1） A. O(0) C. O(n)

B. O(1) D. O(n)

2

4.设A是一个线性表(a1,a2,?,an)，采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为 B ，平均每删除一个元素需要移动的元素个数为

A ；若元素插在ai与ai+1之间(0≤I≤n-1)的概率为

2(n?i)n(n?1)，则平均每插入一个元素所要移动的元素个数为

C ；

n?1 22n?1C.

3A. A. logn C. 2

n/2

B.

n2

D.

3n?1 45.下列函数中，按它们在

n??时的无穷大阶数，最大的是 D 。

B. nlogn D. n!

6.将下图所示的s所指结点加到p所指的结点之后，其语句应为： 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 。 A. n C. n-1

B. 2n-1

D. 2n

8.下面的程序段是合并两个无头结点链表(ha和 hb)为一个无头结点链表ha的过程，作为参数的两个链表都是按结点的data域由大到小链接的。合并后新链表的结点仍按此方式链接。请填写下述空框，使程序能正确运行。

#define NULL 0 typedef struct node{

word文档 可自由复制编辑

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

(6) hb=hb->next (8) p->next=ha

(4) hb (5) p->next

(7) p->next=hb

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; (1) ; while( (2) )

word文档 可自由复制编辑

}

if(pa->data=pb->data) (3) ; else

(4) ;

(5) ;

参考答案：

(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 = n; (3) ; }

return(head); }

void Josephus(int n, int j, int m){

linklisttype *p, *q;

/*建立从尾链到首的环形结构*/

p->data = I;

q = (linklisttype *)malloc(sizeof(linklistttype)); (1) ; (2) ;

word文档 可自由复制编辑

int j;

p = create_link_list(n); for(;I>1;I--) (4) ; while(j

for(I=1;I<=m-1;I++) (5) ;

printf(“?”,q->data); (6) ;

p = p->next;

p = p->next;

}

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){ }

NODE *difference(NODE *A ,NODE *B){

NODE *C,*last;

C=last=(NODE *)malloc(sizeof(NODE)); while( (1) )

if(A->data < B->data){

last=append(last,A->data);

last->next=(NODE *)malloc(sizeof(NODE)); last->next->data=x; return(last->next);

word文档 可自由复制编辑

} else

A=A->next;

if( (2) ){ } else

(3) ; A=A->next; B=B->next;

while( (4) ){ }

(5) ; last=C; C=C->next; free(last); return(C);

last=append(last,A->data); A=A->next;

}

参考答案：

(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( (1) ){ if(L->elem[i]!=L->elem[j]) {

if(j!=(i+1)) (2) ;

L->length=L->length-(j-i-1); }

(3) ;

word文档 可自由复制编辑

本文来源：https://www.bwwdw.com/article/dh53.html