计算机软件技术基础试题
1.线性表的链式存储结构与顺序存储结构相比优点是    CD      ;
A. 所有的操作算法实现简单        B. 便于随机存取
C. 便于插入和删除                D. 便于利用零散的存储器空间
2.线性表是具有n个    C      的有限序列;
A. 表元素        B. 字符            C. 数据元素
D. 数据项                        E. 信息项
3.若长度为n的线性表采用顺序存储结构,在其第I个位置插入一个新元素的算法的时间复杂度为      C    ;1≤I≤n+1
A. O0                            B. O1
C. On                            D. On2
4.设A是一个线性表a1,a2,…,an,采用顺序存储结构,则在等概率的前提下,平均每插入一个元素需要移动的元素个数为    B      ,平均每删除一个元素需要移动的元素个数为
    A      ；若元素插在ai与ai+1之间0≤I≤n-1的概率为,则平均每插入一个元素所要移动的元素个数为    C      ；
A.                             B.
C.                             D.
5.下列函数中,按它们在时的无穷大阶数,最大的是    D      ;
A. logn                                B. nlogn
C. 2n/2                                D. n
6.将下图所示的s所指结点加到p所指的结点之后,其语句应为：    D    ;
A. s->next=p+1; p->next=s;
B. p.next=s; s.;
C. s->next=p->next; p->next=s->next;
D. s->next=p->next; p->next=s;
7.将两个各有n个元素的有序表归并为一个有序表时,其最少的比较次数是    A    ;
A. n                            B. 2n-1
C. n-1                            D. 2n
8.下面的程序段是合并两个无头结点链表ha和 hb为一个无头结点链表ha的过程,作为参数的两个链表都是按结点的data域由大到小链接的;合并后新链表的结点仍按此方式链接;请填写下述空框,使程序能正确运行;
define NULL 0
typedef struct node{
    int data;
    struct node next;
}node, linklisttype;
void combinelinklisttype ha, linklisttype hb{
    linklisttype h, p;
    h = linklisttype mallocsizeoflinklisttype;
    h->next = NULL;
    p = h;
    whileha = NULL && hb = NULL
    ifha->data>=hb->data{            /较大的元素先插入/
        p->next =      1    ;
p =       2    ;
      3    ;
        }
        else{
        p->next =      4    ;
p =       5    ;
      6    ;
}
    ifha==NULL      7    ;
    ifhb==NULL      8    ;
    ha = h->next;
    freeh;
}
参考答案：    1 ha        2 p->next            3 ha=ha->next
            4 hb        5 p->next            6 hb=hb->next
            7 p->next=hb                    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 inclusionlinklisttype ha, linklisttype hb{
    linklisttype pa, pb;
    pa = ha->next;
    pb = hb->next;
          1    ;
    while      2   
        ifpa->data=pb->data          3    ;
        else                          4    ;
          5    ;
}
参考答案：
1 ifpa==NULL returntrue
2 pb=NULL && pa->data>=pb->data
3 returninclusionpa, pb
4 pb = pb->next;
5 returnfalse
10.在本题的程序中,函数create_link_listn建立一个具有n个结点的循环链表；函数josephusn,I,m对由create_link_listn所建立的具有n个结点的循环链表按一定的次序逐个输出,并删除链表中的所有结点;参数nn>0指明循环链表的结点个数,参数I1≤I≤n指明起始结点,参数mm>0是步长,指明从起始结点或前次被删除并输出的结点之后的第m个结点作为本次被输出并删除的结点;例如,对于下图所示的具有6个结点的循环链表,在调用josephus6,3,2后,将输出5,1,3,6,4,2;请在空框处填上适当内容,每框只填一个语句;
define NULL 0
typedef struct node{
    int data;
    struct node next;
}node, linklisttype;
linklisttype create_link_listint n{
    linklisttype head, p, q;
    int I;
    head = NULL;
    ifn>0{
    head = linklisttype mallocsizeoflinklisttype;
    p = head;
    forI=1;I<=n-1;I++{    /此循环用于建立一个链表,链表的内容从1至n-1/
    p->data = I;
    q = linklisttype mallocsizeoflinklistttype;
          1    ;
          2    ;
}
p->data = n;
      3    ;            /建立从尾链到首的环形结构/
}
returnhead;
}
void Josephusint n, int j, int m{
    linklisttype p, q;
    int j;
    p = create_link_listn;
    for;I>1;I--    p = p->next;
          4    ;
    whilej<n{
        forI=1;I<=m-1;I++    p = p->next;
              5    ;
        printf“%8d”,q->data;
      6    ;
        freeq;
        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.在下列程序中,函数differenceA,B用于求两集合之差C=A-B,即当且仅当e是A中的一个元素,且不是B中的元素时,e是C中的一个元素;集合用有序链表实现,用一个空链表表示一个空集合,表示非空集合的链表根据元素之值按递增排列,执行C=A-B之后,表示集合A和B的链表不变,若结果集合C非空,则表示它的链表应根据元素之值按递增序排列;函数append用于在链表中添加结点;
include <stdio.h>
define NULL 0
typedef struct node{
    int data;
    struct node next;
}NODE;
NODE appendNODE last, int x{
    last->next=NODE mallocsizeofNODE;
    last->next->data=x;
    returnlast->next;
}
NODE differenceNODE A ,NODE B{
    NODE C,last;
    C=last=NODE mallocsizeofNODE;
    while      1   
        ifA->data < B->data{
    last=appendlast,A->data;
    A=A->next;
}
else
    if      2    {
        A=A->next;
        B=B->next;
    }
    else
              3    ;
    while      4    {
    last=appendlast,A->data;
    A=A->next;
}
      5    ;
last=C;
C=C->next;
freelast;
returnC;
}
参考答案：
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 elemMAXSIZE;
int length;/表长/
}sqlisttype;
void exam21sqlisttype L{
    int I,j;
    I=2,j=1;
    while      1    {
    ifL->elemI<>L->elemj{
          2    ;
          3    ;
}
I++;
}
      4    ;
}
参考答案：
1 i<=L->length
2
3 j++;
4
13.用单链表表示的链式队列的队头在链表的      A    位置;
A. 链头            B. 链尾            C. 链中
14.若用单链表表示队列,则应该选用      B    ;
A. 带尾指针的非循环链表            B. 带尾指针的循环链表
C. 带头指针的非循环链表            D. 带头指针的循环链表
15.在解决计算机主机与打印机之间速度不匹配问题时,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则从该缓冲区中取出数据打印,先放入打印缓冲区的数据先被打印;该缓冲区应该是一个      B    结构;