《计算机软件技术基础》复习题
1 ?线性表的链式存储结构与顺序
存储结构相比优点是 —CD A.所有的操作算法实现简单
C. 便于插入和删除 2. 线性表是具有n个—二 A.表元索 D. 数据项
B.字符
B. 便于随机存取
D. 便于利用零散的存储器空间
的有限序列。
C. 数据元索 E. 信息项
3. 若长度为n的线性表采用顺序存储结构，在其第I个位匱插入一个新元素的算法的时间复
杂度为 C 。(lWIWn+1)
A. 0(0) C. 0(n)
4?设A是一个线性表(a】,a2,…，an),
B. 0 仃) D. 0(n2)
采用顺序存储结构，则在等概率的前提下，平均每插入
B _____ ,平均每删除一个元素需要移动的元素个数为
一个元素需要移动的元素个数为
；若元素插在&与亦Z间(OWIWn-1)的概率为23二”,则平均每插入一个 n{n
+1)
元素所要移动的元素个数为—C
A. 口
it
C. ----------
2 2n +1 3
B. D.
2
3/1 +1 4
下列函数中，按它们在D
5.
moo时的无穷大阶数，最大的是 A. log/? C. 2n\2
B. nl D. n!
6. 将下图所示的s所指结点加到p所指的结点Z后，其语句应为：—D
nex t nex t
nex t
A. s->next=p+l; 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~l
B. 2n~l D. 2n
&下面的程序段是合并两个无头结点链表(ha和hb)为一个无头结点链表ha的过程，作为 参数的两个链表祁是按结点的chUi域由人到小链接的。合并后新链表的结点仍按此方式链
接。请填写下述空框，使程序能正确运行。
^define NULL 0
typedef struct node{ int data;
struct, node *next; }nocle, 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^>clata) {
p->next 二 p = (3)
(1) ⑵
/*较大的元素先插入*/
■
} else {
p->next 二 p =
(4) ⑸
(6)
■
} if(ha==NULL)
if(hb=NULL)
ha = h->next; free(h);
⑺
⑻
参考答案:
⑴ ha ⑷ hb
(2) p->next (5) p->next
⑺ p->next=hb
(3) ha=ha->next hb二hb-〉(6) next (8) p->next=ha
9. 如果表A中所有元素(ab a2, ???, a?)与表B的一个顺序了?表(b, bm,…b“J完全相同(即 ai=bk,a2=bk+i,-a?=bk+n-i),则称表A包含在表B中。设ha, hb为带头结点的单链表,分别表 示有
序表A和B,下面的函数用于判别表A是否包含在表B中,若是，则返1-1 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;
⑴ ；
while ( _______ (2) ____ )
if (pa->data=pb->da ta) ___________ (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个结点的循环链表；函数 josephusfn, I,m)对由create_link_list(n)所建立的具有n个结点的循环链表按一定的次 序逐个输
出，并删除链表屮的所有结点。参数n(n>0)指明循环链表的结点个数，参数1(1 WlWn)指明起始结点，参数m (m>0是步长)，指明从起始结点或前次被删除并输出的结点 Z示的笫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 p = head;
for(I=l ;I<=n-l; I++) { p->data = I;
q = (linklisttype *)malloc(sizeof(linklistttype));
malloc(sizeof(linklisttype));
/*此循环用于建立一个链表，链表的内容从1至n-1*/
仃)
⑵
}
p->dato = n;
； ；
⑶
return(head);
； /*建立从尾链到首的环形结构*/
void Josephus(int n, int j, int m){
linklisttype *p, *q; int j;
p = create_link_list(n); for(:I>1;I―)
⑷ ；
wh订e(j for(1=1;I<=m-1;I++) p = p->next; ______ (5) ____ ； printf( \->data); ⑹ ； free(q); j二j+1； } } p 二 p->next; 参考答案： (1) p->next = q; (2) p = q； (3) p->next 二 head ⑷j=0 (5) q二p->next; (6) p-〉next = q-〉next 11. 在下列程序中,函数difference (A, B)用于求两集合之差C=A~B,即当且仅当e是A中的 一个元素，且不是B屮的元素时，e是C屮的一个元素。集合用有序链表实现，用一个空链 表表示一个空集合，表示非空集合的链表根据元素之值按递增排列，执行OA-BZ后，表示 集合A和B的链表不变，若结果集合C非空,则表示它的链表应根据元索Z值按递增序排列。 函数append()用于在链表屮添加结点。 #inc]ude 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) { NODE *C,*last; C二last二(NODE malloc(sizeof(NODE)); while ( ______ (1) ____ ) if(A->data < B->data){ last=appcnd(last, A->data);
相关推荐：
loading