东农18秋《数据结构》离线作业

[复制链接]
发表于 2018-11-17 19:48:09 | 显示全部楼层 |阅读模式
东北农业大学网络教育学院
数据结构网上作业题
第一章 绪论
一、选择题:
1、在数据结构中,从逻辑上可以把数据结构分成(  )。
A、动态结构和静态结构                        B、紧凑结构和非紧凑结构
C、线性结构和非线性结构                        D、内部结构和外部结构
2、算法分析的两个主要方面是(  )。
A、空间复杂性和时间复杂性                B、正确性和简明性
C、可读性和文档性                                D、数据复杂性和程序复杂性
3、以下与数据的存储结构无关的术语是(    )。
A、循环队列                B、链表                C、哈希表        D、栈
4、以下数据结构中,哪一个是线性结构(    )。
A.广义表                B、二叉树        C、稀疏矩阵                D、串
5、在下面的程序段中,对x的赋值语句的频度为(    )。
FOR i:=1  TO  n  DO
    FOR j:=1  TO  n  DO   
      x:=x+1;
A、O(2n)                B、O(n)                         C、O(n2)                 D、O(log2n)
6、以下哪个数据结构不是多型数据类型(    )。
A、栈                B、广义表                C、有向图                D、字符串
7、以下数据结构中,(    )是非线性数据结构。
A、树                B、字符串                C、队                        D、栈
8、以下属于逻辑结构的是(    )。
A、顺序表        B. 哈希表                C、有序表                D、单链表
9、下列程序段的时间复杂度为(    )。
   s=0;
   for(i=1;i<n;i++)
    for(j=1;j<n;j++)
       s+=ij;
A、O(1)                        B、O(n)                C、O(2n)                D、O(n2)
10、数据结构是(  )。
A、一种数据类型                  B、相互之间存在一种或多种特定关系的数据元素的集合
C、一组性质相同的数据元素的集合  D、数据的存储结构
11、算法分析的目的是(  )。
A、辨别数据结构的合理性             B、评价算法的效率
C、研究算法中输入与输出的关系       D、鉴别算法的可读性
12、下面程序段的时间复杂度为(  )。
        for(int i=0; i<m; i++)
            for(int j=0; j<n; j++)
                a[i][j]=ij;
A、O(m2)                 B、O(n2)                C、O(mn)                 D、O(m+n)
13、执行下面程序段时,执行S语句的次数为(  )。
        for(int i=1; i<=n; i++)
            for(int j=1; j<=i; j++)
                S;
A、n2                B、n2/2                        C、n(n+1)                 D、n(n+1)/2
14、算法的可读性是指(  )。
A、算法所含语句数较少
B、算法较简单,计算机容易编译
C、算法较简单,人们很容易看出它的执行结果
D、算法结构清晰,容易被算法设计者及其同行看懂
15、算法分析的主要任务是分析(  )。
A、算法是否具有较好的可读性      B、算法中是否存在语法错误
C、算法的功能是否符合设计要求    D、算法的执行时间和问题规模之间的关系
二、填空题:
1、在数据逻辑结构的二元组S=(D,R)表示中,D是(   ),R是(  )。
2、没有前驱的结点称为(  ),没有后继的结点称为(   )。
3、数据的逻辑结构可以分为(   )和(   )两大类。
4、在树形结构中,每个结点最多只有一个(   )。
5、为了实现随机访问,线性结构应该采用(   )存储。
6、逻辑上相邻的结点在存储器中也相邻,这是(   )存储结构的特点。
7、数据的运算是在(   )上定义的,运算的具体实现与(   )结构有关。
8、用数量级形式表示的算法执行时间称为算法的(   )。
9、算法的执行时间是(   )的函数。
10、在高级语言程序中,表示一组连续的存储单元,通常用(   )。
11、数据的物理结构包括(   )的表示和(   )的表示。
12、对于给定的n个元素,可以构造出的逻辑结构有(   ),(   ),(   ),(   )四种。
13、一个算法具有5个特性: (   )、(   )、(   )、有零个或多个输入、有一个或多个输出。
14、一个算法的时间复杂度为(3n2+2nlog2n+4n-7)/(5n),其数量级表示为(   )。
15、在线性结构、树形结构和图形结构中,前驱和后继结点之间分别存在着( )、( )和( )的联系。
三、判断题:
1、计算机程序处理的对象可分为数据和非数据两大类。(  )
2、构成数据的最小单位是数据项。(  )
3、数据元素和结点是同一个概念。(  )
4、每个结点一般包含若干个字段。(  )
5、同一个结点中的各个字段类型可以不相同。(  )
6、数据是由一些类型相同的数据元素构成的。(  )
7、数据的逻辑结构与各数据元素在计算机中如何存储有关。(  )
8、如果数据元素值的大小改变了,则数据的逻辑结构也随之改变。(  )
9、逻辑结构相同的数据,结点类型也一定相同。(  )
10、逻辑结构相同的数据,可以有多种不同的存储方法。(  )
11、逻辑结构不相同的数据,要采用不同的存储方法来存储。(  )
12、线性结构的特征之一是:开始结点和终端结点都是唯一的。(  )
13、在线性结构中,每个结点都有一个前驱、一个后继。(  )
14、线性结构可以看成是树形结构的一个简单特例。(  )
15、树型结构可以看成是图状结构的一个简单特例。(  )
16、判断某个算法是否容易阅读是算法分析的任务之一。(  )
17、算法容易阅读是好算法的主要标志之一。(  )
18、算法必须用程序设计语言来书写。(  )
19、为了实现随机访问,线性结构只能用顺序方法存储。(  )
20、问题的规模越大,其算法也就越长。(  )
21、数据元素是数据的最小单位。(    )
22、记录是数据处理的最小单位。 (    )
23、数据的逻辑结构是指数据的各数据项之间的逻辑关系;(   )
24、算法的优劣与算法描述语言无关,但与所用计算机有关。(    )
25、健壮的算法不会因非法的输入数据而出现莫名其妙的状态。(    )
26、算法可以用不同的语言描述,如果用C 语言或PASCAL语言等高级语言来描述,则算法实际上就是程序了。(    )
27、程序一定是算法。(    )
28、数据的物理结构是指数据在计算机内的实际存储形式。(   )
29、在顺序存储结构中,有时也存储数据结构中元素之间的关系。(    )
30、顺序存储方式的优点是存储密度大,且插入、删除运算效率高。(    )四、应用题:
1、评价一个好的算法,您是从哪几方面来考虑的?2、若有100个学生,每个学生有学号,姓名,平均成绩,采用什么样的数据结构最方便,写出这些结构?3、在编制管理通讯录的程序时,什么样的数据结构合适? 为什么?4、有下列运行时间函数:
(1)T1 (n)=1000;    (2)T2(n)=n2+1000n;     (3)T3(n)=3n3+100n2+n+1;
        分别写出相应的大O表示的运算时间。
五、综合题:
1、设计一数据结构,用来表示某一银行储户的基本信息: 账号、姓名、开户年月日、储蓄类型、存入累加数、利息、帐面总数。
2、调用下列C函数f(n)或PASACAL函数f(n),回答下列问题:
(1)试指出f(n)值的大小,并写出f(n) 值的推导过程;
(2)假定n= 5,试指出f(5)值的大小和执行f(5)时的输出结果。
    C函数: int f(int  n)
             { int i,j,k,sum= 0;
              for(i=l; i<n+1;i++)
               {for(j=n;j>i-1; j--)
                 for(k=1;k<j+1;k++ )
sum++;
                 printf("sum=%d\n",sum);
}
              return (sum);
}
第二章 线性表
一、选择题:
1、一个顺序表所占存储空间的大小与(  )无关。
A、顺序表长度           B、结点类型     C、结点中各字段的类型   D、结点存放顺序
2、设内存地址的分配是从小(低地址)到大(高地址)进行的。若存储某结点需要5个内存单元,则该结点的地址,通常是指5个内存单元中(  )。
A、第3个单元的地址     B、地址值最小的那个单元的地址
C、地址的一个升序序列   D、地址的一个降序序列。
3、顺序表的长度与(  )有关。
A、线性表中有多少个结点    B、每个结点有多少个字段
C、每个结点中各字段的类型  D、存储顺序表的数组类型
4、与单向链表相比,双向链表的优点之一是(  )。
A、插入、删除操作更简单        B、可以进行随机访问
C、可以省略表头指针或表尾指针  D、顺序访问相邻结点更灵活
5、动态链表所占用的内存单元地址一定是(  )。
A、无序的   B、连续的  C、不连续的   D、部分连续的
6、与动态链表相比,静态链表的缺点之一是(  )。
A、插入、删除操作有时不方便    B、存储空间有时得不到充分利用
C、要求各结点具有相同的类型    D、链表中各结点的值只能读取,不能更改
7、如果对线性表的运算只有2种:删除第一个元素;在最后一个元素的后面插入新元素,则最好使用(  )。
A、只有表头指针没有表尾指针的循环单向链表  B、只有表尾指针没有表头指针的循环单向链表
C、非循环双向链表                          D、循环双向链表
8、设H是带表头结点循环单向链表的表头指针。当这种链表成为空链表时,(  )。
A、表头结点指针字段的值为空
B、H的值为空
C、表头结点指针字段的值与H的值相等
D、表头结点指针字段的值与H的地址相等
9.设H是带表头结点循环单向链表的表头指针,p是和H同类型的变量。当p指向链表的最后一个结点时,(  )。
A、该结点指针字段的值为空
B、p为空
C、p的值与表头结点指针字段的值相等
D、该结点指针字段的值与H的值相等
10.在长度为n的(  )上,删除第一个元素,其算法的时间复杂度是O(l)。
A、只有表头指针的不带表头结点的循环单向链表
B、只有表尾指针的不带表头结点的循环单向链表
C、只有表尾指针的带表头结点的循环单向链表
D、只有表头指针的带表头结点的循环单向链表
11.在长度为n的(  )上,删除最后一个元素,其算法的时间复杂度是O(n)。
A、只有表头指针的循环双向链表    B、只有表头指针的非循环双向链表
C、只有表尾指针的非循环双向链表  D、只有表尾指针的循环双向链表
12、假设某个带头结点的单链表的头指针为head,则判定该表为空表的条件是(  )。
A、head==NULL;        B、head->next==NULL;
C、head!=NULL;        D、head->next==head;
13、已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点,则在s所指结点之后插入上述链表应执行的语句为(  )。
A、q->next=s->next;s->next=p;        B、s->next=p;q->next=s->next;
C、p->next=s->next;s->next=q;        D、s->next=q;p->next=s->next;
14、在线性表的下列运算中,不改变数据元素之间结构关系的运算是( )。
A、插入 B、删除    C、排序  D、定位
15、下列有关线性表的叙述中,正确的是(   )。
A、一个线性表是n个数据元素的有限序列
B、线性表中任何一个元素有且仅有一个直接前驱
C、线性表中任何一个元素有且仅有一个直接后继
D、以上说法都不正确
16、从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时,需向前移动(  )个元素。
A、n-i                        B、n-i+1                        C、n-i-1                        D、i
17、在一个单链表HL中,若要向表头插入一个由指针p指向的结点,则执行(  )。
A、HL=p; p->next=HL;         B、p->next=HL; HL=p;
C、p->next=HL; p=HL;         D、p->next=HL->next; HL->next=p;
18、下述哪一条是顺序存储结构的优点?(    )
A、存储密度大  B、插入运算方便  C、删除运算方便  D、可方便地用于各种逻辑结构的存储表示
19、关于线性表的叙述中,错误的是哪一个?(    )
A、线性表采用顺序存储,必须占用一片连续的存储单元。
B、线性表采用顺序存储,便于进行插入和删除操作。
C、线性表采用链接存储,不必占用一片连续的存储单元。
D、线性表采用链接存储,便于插入和删除操作。
20.线性表是具有n个(    )的有限序列(n>0)。
A、表元素      B、字符      C、数据元素     D、数据项
21.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用(    )存储方式最节省时间。
A、顺序表      B、双链表        C、带头结点的双循环链表     D、单循环链表
22、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用(    )存储方式最节省运算时间。
A、单链表     B、仅有头指针的单循环链表     C、双链表       D、仅有尾指针的单循环链表
23、设一个链表最常用的操作是在末尾插入结点和删除尾结点,则选用(   )最节省时间。
A、单链表   B、单循环链表   C、带尾指针的单循环链表   D、带头结点的双循环链表
24、若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用(    )存储方式最节省运算时间。
A、单链表      B、双链表     C、单循环链表     D、带头结点的双循环链表
25、静态链表中指针表示的是(    )。
A. 内存地址       B、数组下标     C、下一元素地址      D、左、右孩子地址
26、链表不具有的特点是(    )。
A、插入、删除不需要移动元素  B、可随机访问任一元素
C、不必事先估计存储空间  D、所需空间与线性长度成正比
27、下面的叙述不正确的是(    )。
A、线性表在链式存储时,查找第i个元素的时间同i的值成正比
B、线性表在链式存储时,查找第i个元素的时间同i的值无关
C、线性表在顺序存储时,查找第i个元素的时间同i 的值成反比
D、线性表在顺序存储时,查找第i个元素的时间同i的值无关
28、若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为(    )(1<=i<=n+1)。
A. O(0)      B. O(1)         C. O(n)          D. O(n2)
29、对于顺序存储的线性表,访问结点和增加、删除结点的时间复杂度为(    )。
A、O(n)  O(n)      B、O(n)  O(1)       C、O(1)  O(n)        D、O(1)  O(1)
30、在单链表指针为p的结点之后插入指针为s的结点,正确的操作是(    )。
A、p->next=s;s->next=p->next;                B、s->next=p->next;p->next=s;
C、p->next=s;p->next=s->next;                D、p->next=s->next;p->next=s;二、填空题:
1、顺序表是一种(  )线性表。
2、往长度为n的顺序表中插入一个元素,最多要移动(  )个元素。
3、在(  )情况下,从顺序表中删除一个元素平均要移动近一半的元素。
4、在程序中,实现动态链表要用到(  )类型的变量。
5、用数组实现的链表,通常称为(  )链表。
6、若用带表头结点的单向链表来表示长度为n的线性表,则需要为链表分配(  )个结点的内存空间。
7、在循环单向链表中,可以用(  )代替表头指针。
8、在长度为n的顺序表上实现定位操作,其算法的时间复杂度是(  )。
9、在长度为n的单向链表上实现定位操作,其算法的时间复杂度是(  )。
10、在顺序表(  )后面插人新元素,不需要移动任何元素。
11、在(  )循环单向链表上,删除第一个结点,其算法的时间复杂度为O(l)。
12、根据(  )多少,线性链表可分为单向链表和双向链表两大类。
13、在单向链表中,增加一个表头结点的目的是(  )。
14、用数组实现单向链表时,通常将数组中那些空单元组织成一个(  )。
15、往顺序表中插入新元素,除了要判断是否有空单元以外,还要判断(  )是否正确。
16、在非循环的(  )链表中,可以用表尾指针代替表头指针。
17、在一个长度为100的顺序表中删除第10个元素时,需移动(  )个元素。
18、在以HL为表头指针的带表头附加结点的单链表和循环单链表中,链表为空的条件分别为( )和( )。
19、当线性表的元素总数基本稳定,且很少进行插入和删除操作,但要求以最快的速度存取线性表中的元素时,应采用(  )存储结构。
20、线性表L=(a1,a2,…,an)用数组表示,假定删除表中任一元素的概率相同,则删除一个元素平均需要移动元素的个数是(  )。
21、设单链表的结点结构为(data,next),next为指针域,已知指针px指向单链表中data为x的结点,指针py指向data为y的新结点 , 若将结点y插入结点x之后,则需要执行以下语句: (  );(  )。
22、在一个长度为n的顺序表中第i个元素(1<=i<=n)之前插入一个元素时,需向后移动(  )个元素。
23.在单链表中设置头结点的作用是(  )。
24.对于一个具有n个结点的单链表,在已知的结点p后插入一个新结点的时间复杂度为(  ),在给定值为x的结点后插入一个新结点的时间复杂度为(  )。
25.根据线性表的链式存储结构中每一个结点包含的指针个数,将线性链表分成(  )和(  );而又根据指针的连接方式,链表又可分成(  )和(  )。
26、在双向循环链表中,向p所指的结点之后插入指针f所指的结点,其操作是(  )、(  )、(  )、(  )。
27、链接存储的特点是利用(  )来表示数据元素之间的逻辑关系。
28、顺序存储结构是通过(  )表示元素之间的关系的;链式存储结构是通过(  )表示元素之间的关系的。
29、对于双向链表,在两个结点之间插入一个新结点需修改的指针共(  )个,单链表为(  )个。
30、循环单链表的最大优点是:(  )。
31、已知指针p指向单链表L中的某结点,则删除其后继结点的语句是:(  )
32、带头结点的双循环链表L中只有一个元素结点的条件是:(  )
33、在单链表L中,指针p所指结点有后继结点的条件是:(  )
34、带头结点的双循环链表L为空表的条件是:(  )。
35、在单链表p结点之后插入s结点的操作是:(  )。三、判断题:
1、线性结构中的结点按前驱、后继关系可以排成一个线性序列。(   )
2、存储一个线性表所需的内存单元数与线性表的元素类型有关。(   )
3、空线性表的一个特征是线性表中各结点尚未赋值。(   )
4、顺序表是一种有序的线性表。(   )
5、顺序表的长度等于元素个数与每个元素所占内存单元数之乘积。(   )
6、分配给顺序表的内存单元地址必须是连续的。(   )
7、用一维数组表示顺序表时,顺序表的第i个元素必须放在下标为i的数组元素中。(   )
8、若表示顺序表的一维数组各元素尚未赋值,则创建一个空顺序表的操作实际上不需要做任何事情。(   )
9、从长度为n的顺序表中删除一个元素,所需时间都是O(n)。(   )
10、往顺序表中插入一个元素,平均要移动大约一半的元素。(   )
11、在动态单向链表中,每个结点总是占用一片连续的内存空间。(   )
12、分配给单向链表的内存单元地址必须是连续的。(   )
13、与顺序走相比;在链表上实现顺序访问,其算法的效率比较低。(   )
14、单向链表中的结点只有后继,没有前驱。(   )
15、在任何一种线性链表上都无法进行随机访问。(   )
16、在循环单向链表中;每个结点都有一个后继。(   )
17、在画单向链表示意图时,表示指针的箭头必须指向结点的第一个字段。(   )
18、凡是空的单向链表都是不含任何结点的。(   )
19、空的单向链表所表示的是长度为零的线性表。(   )
20.允许进行插入、删除操作是动态链表的主要特征。(   )
21、一个结点的指针字段为空,说明该字段中没有存放任何信息。(   )
22、不带表头结点的空的单向链表不占用任何内存空间。(   )
23、在描述单向链表的结点类型时,必须首先描述数值字段,然后再描述指针字段。(   )
24、如果单向链表带有表头结点,则线性表的插入操作永远不会改变表头指针的值。(  )
25、在循环单向链表中,任何一个结点的指针字段值都不可能为空。(   )
26、双向链表的表头指针要比单向链表的表头指针占用更多的内存空间。(   )
27、在结点个数相同的情况下,双向链表所需的内存空间是单向链表的两倍。(   )
28、双向链表的结点,数值字段、前驱指针字段和后继指针字段的排列顺序可以是任意的。(   )
29、在双向链表中,每个结点一般至少有3个字段。(   )
30、静态链表的表头指针是一个指针类型的变量。(   )
31、链表中的头结点仅起到标识的作用。(   )
32、顺序存储结构的主要缺点是不利于插入或删除操作。(  )
33、线性表采用链表存储时,结点和结点内部的存储空间可以是不连续的。(    )
34、顺序存储方式插入和删除时效率太低,因此它不如链式存储方式好。(    )
35、对任何数据结构链式存储结构一定优于顺序存储结构。(  )
36、顺序存储方式只能用于存储线性结构。(    )
37、集合与线性表的区别在于是否按关键字排序。(    )
38、所谓静态链表就是一直不发生变化的链表。(    )
39、线性表的特点是每个元素都有一个前驱和一个后继。(    )
40、取线性表的第i个元素的时间同i的大小有关. (    )
41、循环链表不是线性表. (    )
42、线性表只能用顺序存储结构实现。(    )
43、线性表就是顺序存储的表。(    )
44、为了很方便的插入和删除数据,可以使用双向链表存放数据。(    )
45、顺序存储方式的优点是存储密度大,且插入、删除运算效率高。(    )
四、应用题:
1、线性表有两种存储结构:一是顺序表,二是链表。试问:
(1)如果有 n个线性表同时并存,并且在处理过程中各表的长度会动态变化,线性表的总数也会自动地改变。在此情况下,应选用哪种存储结构? 为什么?(2)若线性表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取线性表中的元素,那么应采用哪种存储结构?为什么?2、说明在线性表的链式存储结构中,头指针与头结点之间的根本区别;头结点与首元结点的关系。3、在单链表和双向链表中,能否从当前结点出发访问到任何一个结点?4、设单链表中某指针p所指结点(即p结点)的数据域为data,链指针域为next,请写出在p结点之前插入s结点的操作5、设双向循环链表中结点的数据域、前驱和后继指针域分别为data,pre和next,试写出在指针p 所指结点之前插入一s结点的C语言描述语句。
五、综合题:
1、假设有两个按元素值递增次序排列的线性表,均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表,并要求利用原来两个单链表的结点存放归并后的单链表。2、已知L1、L2分别为两循环单链表的头结点指针,m,n分别为L1、L2表中数据结点个数。要求设计一算法,用最快速度将两表合并成一个带头结点的循环单链表。3、已知不带头结点的线性链表list,链表中结点构造为(data、link),其中data为数据域,link为指针域。请写一算法,将该链表按结点数据域的值的大小从小到大重新链接。要求链接过程中不得使用除该链表以外的任何链结点空间。
4、试编写在带头结点的单链表中删除(一个)最小值结点的(高效)算法。void  delete(Linklist  &L)
5、给定(已生成)一个带表头结点的单链表,设head为头指针,结点的结构为(data,next),data为整型元素,next为指针,试写出算法:按递增次序输出单链表中各结点的数据元素,并释放结点所占的存储空间。(要求;不允许使用数组作辅助空间)第三章  栈和队列
一、选择题:
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、循环双向链表
6、最不适合用作链接栈的链表是(    )。
A、只有表头指针没有表尾指针的循环双向链表 B、只有表尾指针没有表头指针的循环双向链表
C、只有表尾指针没有表头指针的循环单向链表D、只有表头指针没有表尾指针的循环单向链表
7、若 5个元素的进栈序列是  1,2,3,4,5,则不可能得到出栈序列(    )。
A、1,2,3,4,5     B、3,4,2,5,1    C、4,2,1,3,5     D、5,4,3,2,1
8、若5个元素的出栈序列是1,2,3,4,5,则进栈序列可能是(    )。
A、3,1,2,5,4    B、2,3,1,5,4    C、3,l,4,2,5    D、2,4,3,1,5
9、当4个元素的进栈序列给定以后,由这4个元素构成的可能的出栈序列共有(    )种。
A、14       B、16        C、17                    D、24
10、链接栈和链接队列都可以用只带表尾指针的循环单向链表来表示。此时的栈和队列(    )。
A、插入运算和删除运算都相同     B、删除运算相同,插入运算不相同
C、插入运算相同,删除运算不相同 D、插人运算和删除运算都不相同
11、设n个元素的进栈序列是1,2,3,…,n,出栈序列是p,p,…,p。若p=n,则p(l≦i<n)的值(    )。
A、是i            B、是n-i          C、是n-i+1           D、有多种可能
12、设n个元素的进栈序列是1,2,3,…,n,出栈序列是p,p,…,p。若p=n,则p(l≦i<n)的值(    )。
A、是i           B、是n-i          C、是n-i+1           D、有多种可能
13.设n个元素的进栈序列是p,p,…,p,出栈序列是1,2,3,…,n,。若p=l,则p的值(    )。
A、可能是2           B、一定是2            C、不可能是2                  D、不可能是3
14、与顺序队列相比,链接队列的(    )。
A、优点是可以实现无限长队列     B、优点是插人、删除操作较简单
C、缺点是不能进行顺序访问       D、缺点是不能根据队首指针和队尾指针计算队列的长度
15、如果栈和队列都用只带表尾指针的循环单向链表来表示。则栈和队列的(    )。
A、删除算法相同,插入算法不相同    B、插人算法相同,删除算法不相同
C、插入算法相同,删除算法也相同    D、插人算法不相同,删除算法也不相同
16、循环顺序队列中是否可以插入下一个元素,(    )。
A、与队首指针和队尾指针的值有关
B、只与队尾指针的值有关,与队首指针的值无关
C、只与数组大小有关,与队首指针和队尾指针的值无关
D、与曾经进行过多少次插入操作有关
17、在顺序队列中,元素的排列顺序(    )。
A、由元素插入队列的先后顺序决定     B、与元素值的大小有关
C、与队首指针和队尾指针的取值有关   D、与数组大小有关
18、假设以数组A[n]存放循环队列的元素,其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素,头指针指向队列中队头元素的前一个位置,则当前存于队列中的元素个数为(    )。
A、(rear-front-1)%n        B、(rear-front)%n
C、(front-rear+1)%n        D、(rear-front+n)%n
19、在计算机内实现递归算法时所需的辅助数据结构是(    )。
A、栈                B、队列                C、树                D、图
20、假设以数组A[m]存放循环队列的元素。已知队列的长度为length,指针rear指向队尾元素的下一个存储位置,则队头元素所在的存储位置为(    )。
A、(rear-length+m+1)%m        B、(rear-length+m)%m
C、(rear-length+m-1)%m        D、(rear-length)%m
21、当利用大小为n的数组顺序存储一个队列时,该队列的最大长度为(    )。
A、n-2                         B、n-1                        C、n                         D、n+1
22、对于栈操作数据的原则是(   )。
A、先进先出                B、后进先出                C、后进后出                D、不分顺序
23、某堆栈的输入序列为a,b,c ,d,下面的四个序列中,不可能是它的输出序列的是(    )。
A、a,c,b,d         B、b,c,d,a    C、c,d,b,a         D、d,c,a,b
24、设计一个判别表达式中左,右括号是否配对出现的算法,采用(    )数据结构最佳。
A、线性表的顺序存储结构       B、队列     C、线性表的链式存储结构       D、栈
25、用链接方式存储的队列,在进行删除运算时(    )。
A、仅修改头指针   B、仅修改尾指针    C、头、尾指针都要修改    D、头、尾指针可能都要修改
26、循环队列存储在数组A[0..m]中,则入队时的操作为(    )。
A、rear=rear+1                                        B、rear=(rear+1)mod(m+1)
C、rear=(rear+1) mod m                        D、rear=(rear+1) mod (m-1)
27、若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0和3,当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为多少?(   )。
A、1和 5         B、2和4          C、4和2         D、5和1  
28、栈和队列的共同点是(    )。
A、都是先进先出                        B、都是先进后出   
C、只允许在端点处插入和删除元素        D、没有共同点
29、最大容量为n的循环队列,队尾指针是rear,队头是front,则队空的条件是(    )。
A、(rear+1) MOD n=front                   B、rear=front
C、rear+1=front                           D、(rear-l) MOD n=front
30、设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5和e6依次通过栈S,一个元素出栈后即进队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e1则栈S的容量至少应该是(   )。
A、6          B、4          C、3          D、2
二、填空题:
1、具有“先进先出”特性的线性表称为(   )。
2、栈是一种具有(   )特性的线性表。
3、用算法语言描述顺序栈时,不但要用(   )表示其存储空间,而且还要用一个变量表示(   )。
4、即使知道队首指针和队尾指针的值,也无法计算出元素个数的队列,一定是(   )队列。
5、如果程序所要处理的数据元素是逐步产生的,而且要求处理数据元素的顺序和产生数据元素的顺序正好相反,则通常用(   )暂存待处理的数据。
6、顺序栈和链接钱的区别仅在于(   )的不同。
7、在编写程序的时候,如果栈的最大长度难以估计,则最好使用(   )。
8、栈和队列的区别仅在于(   )。
9、若用Q[0 ] ~ Q[100]作为循环顺序队列的存储空间,Q[f]、Q[r]分别表示队首元素和下一个插人位置,则当 f=70,r=20时,队列中共有(   )个元素。
10、顺序队列在实现的时候;通常将数组看成是一个首尾相连的环,这样做的目的是为避免产生(   )现象。
11、若用只有队尾指针没有队首指针的循环单向链表来表示链接队列,则在进行删除操作的过程中,不仅需要判断(   ),而且还要判断(   )。
12、若用Q[0] ~ Q[m]作为循环顺序队列的存储空间,Q[r]表示队尾元素,Q[f]表示队首元素的前一个位置,则可以用(   )作队空的标志,与此相对应,可用(   )作队满的标志。
13、队列的队尾位置通常是随着(   )操作而变化的。
14、栈是(   )的线性表,其运算遵循(   )的原则。
15、(   )是限定仅在表尾进行插入或删除操作的线性表。
16、一个栈的输入序列是:1,2,3则不可能的栈输出序列是(   )。
17、设有一个空栈,栈顶指针为1000H(十六进制),现有输入序列为1,2,3,4,5,经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后,输出序列是(   ),而栈顶指针值是(   )H。设栈为顺序栈,每个元素占4个字节。
18、在作进栈运算时应先判别栈是否(   );在作退栈运算时应先判别栈是否(   );当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(   )。
19、多个栈共存时,最好用(   )作为存储结构。
20、用S表示入栈操作,X表示出栈操作,若元素入栈的顺序为1234,为了得到1342出栈顺序,相应的S和X的操作串为(   )。
21、顺序栈用data[1..n]存储数据,栈顶指针是top,则值为x的元素入栈的操作是(   )。
22、表达式23+((123-2)/4+345/7)+108/9的后缀表达式是(   )。
23、循环队列的引入,目的是为了克服(   )。
24、(   )又称作先进先出表。
25、队列的特点是(   )。
26、已知链队列的头尾指针分别是f和r,则将值x入队的操作序列是(   )。
27、区分循环队列的满与空,只有两种方法,它们是(   )和(   )。
28、设循环队列存放在向量sq.data[0:M]中,则队头指针sq.front在循环意义下的出队操作可表示为(   ),若用牺牲一个单元的办法来区分队满和队空(设队尾指针sq.rear),则队满的条件为(   )。
29、表达式求值是(   )应用的一个典型例子。
30、循环队列用数组A[0..m-1]存放其元素值,已知其头尾指针分别是front和rear ,则当前队列的元素个数是(   )。
三、判断题:
1、栈是一种存储方法比较特殊的线性表。(   )
2、栈底元素是不能删除的元素。(   )
3、顺序栈中元素值的大小是有序的。(   )
4、进栈越早的元素,出栈越晚。(   )
5、在n个元素进栈后,它们的出栈顺序和进栈顺序一定正好相反。(   )
6、顺序栈的栈顶指针是一个指针类型的变量。(   )
7、顺序栈是一种规定了元素进栈顺序的栈。(   )
8、对于顺序栈来说,栈底元素的下标不能大于栈顶元素的下标。(   )
9、对于顺序找来说,栈顶指针的类型必须和数组下标的类型相同。(   )
10、栈顶元素和栈底元素有可能是同一个元素。(   )
11、对于非空的栈来说,栈顶元素和栈底元素都是唯一的。(   )
12、对于顺序栈来说,栈顶指针的移动方向只与插人、删除操作有关。(   )
13、若用s[1] ~ s[m]表示顺序栈的存储空间,则对栈的插人、删除操作最多只推进行m次。(  )
14、对顺序栈进行插入、删除操作,不涉及元素的前、后移动问题。(   )
15、栈是一种对插入、删除操作总次数作了限制的线性表。(   )
16、栈是一种对插入、删除操作的次序作了限制的线性表。(   )
17、插入、删除操作比较简单是链接栈的优点之一。(   )
18、如果两个顺序栈有共同的元素,则可以共用同一个数组。(   )
19、栈和队列都不适合用散列存储法存储。(   )
20、栈和队列具有相同的逻辑特性。(   )
21、空栈没有栈顶指针。(   )
22、空栈是指栈中元素尚未赋值。(   )
23、空栈是指栈项指针尚未赋值。(   )
24、n个元素进队列的顺序和出队列的顺序总是一致的。(   )
25、顺序队列中有多少元素,可以根据队首指针的值和队尾指针的值来计算。(   )
26、循环队列中每个元素都有后继。(   )
27、循环队列没有开始结点和终端结点。(   )
28、若用“队首指针的值和队尾指针的值相等”作为循环顺序队列为空的标志,则在设置一个空队列时,只需给队首指针和队尾指针赋同一个值,不管什么值都可以。(   )
29、无论是顺序队列,还是链接队列,插人、删除运算的时间复杂度都是O(1)。(   )
30、若用不带表头结点的非循环单向链表来表示链接队列,则可以用“队首指针的值和队尾指针的位相等”作为队空的标志。(   )
四、应用题:
1、什么是队列的假上溢现象,怎么解决?2、有5 个元素,其入栈次序为:A,B,C,D,E,在各种可能的出栈次序中,以元素C,D最先出栈(即C第一个且D第二个出栈)的次序有哪几个?3、设输入序列为2,3,4,5,6,利用一个栈能得到序列2,5,3,4,6吗?栈可以用单链表实现吗?
4、在一个算法中需要建立多个堆栈时可以选用下列三种方案之一,试问:这三种方案之间相比较各有什么优缺点?
(1)分别用多个顺序存储空间建立多个独立的堆栈;
(2)多个堆栈共享一个顺序存储空间;
(3)分别建立多个独立的链接堆栈。5、设一个双端队列,元素进入该队列的次序为a,b,c,d。求既不能由输入受限的双端队列得到,又不能由输出受限的双端队列得到的输出序列。
五、综合题:
1、设从键盘输入一整数的序列:a1, a2, a3,…,an,试编写算法实现:用栈结构存储输入的整数,当ai≠-1时,将ai进栈;当ai=-1时,输出栈顶整数并出栈。算法应对异常情况(入栈满等)给出相应的信息。
2、假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾结点,但不设头指针,请写出相应的入队列和出队列算法。3、如果允许在循环队列的两端都可以进行插入和删除操作。要求:
(1)写出循环队列的类型定义;
(2)写出“从队尾删除”和“从队头插入”的算法。4、设计算法以求解从集合{1..n}中选取k(k<=n)个元素的所有组合。例如,从集合{1..4}中选取2个元素的所有组合的输出结果为:1  2,1  3,1  4,2  3, 2  4,3  4。
第四章  串
一、选择题:
1、判断两个串大小的基本准则是(   )。
A、两个串长度的大小        B、两个串中首字符的大小
C、两个串中大写字母的多少        D、对应的第一个不等字符的大小
2、通常将链串的结点大小设置为大于1是为了(   )。
A、提高串匹配效率                                                B、提高存储密度
C、便于插入操作                                                        D、便于删除操作
3、设串sl=″Data Structures with Java″,s2=″it″,则子串定位函数index(s1,s2)的值为(   )。
A、15                        B、16                        C、17                        D、18
4、下面关于串的的叙述中,哪一个是不正确的?(    )。
A、串是字符的有限序列                                B、空串是由空格构成的串
C、模式匹配是串的一种重要运算                D、串既可以采用顺序存储,也可以采用链式存储
5、设有两个串p和q,其中q是p的子串,求q在p中首次出现的位置的算法称为(    )。
A、求子串       B、联接       C、匹配         D、求串长
6、若串S=’software’,其子串的数目是(    )。
A、8      B、37          C、36          D、9
7、串的长度是指(    )。
A、串中所含不同字母的个数      B、串中所含字符的个数
C、串中所含不同字符的个数      D、串中所含非空格字符的个数
二、填空题:
1、设S=’I am a teacher’,则其长度为(    )。
2、设s1=’good’,s2=’ ’,s3=’bye!’,则s1,s2,s3连接后的结果是(    )。
3、空格串是指(    ),其长度等于(    )。
4、组成串的数据元素只能是(    )。
5、一个字符串中(    )称为该串的子串 。
6、INDEX(‘DATASTRUCTURE’, ‘STR’)=(    )。
7、设正文串长度为n,模式串长度为m,则串匹配的KMP算法的时间复杂度为(    )。
8、设T和P是两个给定的串,在T中寻找等于P的子串的过程称为(    ),又称P为(    )。
9、串是一种特殊的线性表,其特殊性表现在(    );串的两种最基本的存储方式是(    )、(    )。
10、两个字符串相等的充分必要条件是(    )。
三、判断题:
1、KMP算法的特点是在模式匹配时指示主串的指针不会变小(    )。
2、设模式串的长度为m,目标串的长度为n,当n≈m且处理只匹配一次的模式时,朴素的匹配(即子串定位函数)算法所花的时间代价可能会更为节省(    )。
3、串是一种数据对象和操作都特殊的线性表(    )。
四、应用题:
1、简述空格串与空串的区别。2、如果两个串含有相等的字符,能否说它们相等?五、综合题:
1、编写程序,统计在输入字符串中各个不同字符出现的频度并将结果存入文件(字符串中的合法字符为A-Z这26个字母和0-9这10个数字)。第五章  数组和广义表
一、选择题:
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、矩阵的存储方法
6、特殊矩阵不同于一般的稀疏矩阵,是因为(   )。
A、特殊矩阵中值相同的元素分布有规律   B、特殊矩阵中值相同的元素分布比较密集
C、特殊矩阵中值相同的元素较少         D、特殊矩阵有特殊的用途
7、所谓稀疏矩阵是指(   )的矩阵。
A、零元素较多且分布无规律    B、非零元素较少
C、元素较少                  D、不适合用二维数组表示
8、10阶3对角矩阵用行优先顺序表表示,矩阵中第7行第8列元素在顺序表中(   )。
A、是第20个元素             B、是第21个元素
C、是第22个元素             D、不存在
9、对稀疏矩阵采用压缩存储,其优点之一是可以(   )。
A、减少矩阵的存储空间需求量。     B、减少访问非零元素所需时间
C、减少非零元素的存储空间需求量   D、降低非零元素间逻辑关系的复杂程度
10、矩阵用行优先顺序表表示以后,(   )。
A、减少了存储空间的需求量       B、增加了存储空间的需求量
C、只能按行优先顺序访问矩阵元素D、存取矩阵元素所需时间保持不变
11、5行6列的矩阵,每个元素占2个单元,按行优先顺序存储,起始地址为1000,第 4行第5列的那个元素存储单元首地址是(   )。
A、1046                   B、1044                   C、1048                   D、1023
12、8阶方阵,每个元素占1个单元,按行优先顺序存储,起始地址为100,存储地址为135的那个元素是矩阵中第5行第(   )列元素。
A、2     B、3     C、4   D、5
13、对于一个非空的广义表来说,(   )。
A、可能不含任何原子元素                B、至少含一个原子元素
C、其长度不小于其中任何一个子表的长度  D、至少含一个非空的子表元素
14、在表示广义表L=(())的链接存储结构中,有(   )个结点。
A、0    B、1    C、2     D、3
15、在一个长度为n,含m个原子的广义表中,(   )。
A、m和n相等         B、m不大于n     C、m不小于n          D、m和n无关
16、下列4个广义表中,长度为1,深度为4的广义表是(   )。
A、((),((a)))        B、((((a),b)),c)  C、(((a,b),(c)))    D、(((a,(b),c)))
17、空的广义表,是指广义表(   )。
A、深度为0                                B、尚未赋值     C、不含任何原子                        D、不含任何元素
18、对于广义表((a,b),(()),(a,(b)))来说,其(   )。
A、长度为4                                B、深度为4    C、有3个元素                        D、有2个元素
19、设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一元素,其存储地址为1,每个元素占一个地址空间,则a85的地址为(    )。
A、13               B、33                C、18               D、40
20、假设以行序为主序存储二维数组A=array[1..100,1..100],设每个数据元素占2个存储单元,基地址为10,则LOC[5,5]=(    )。
A、808              B、818              C、1010             D、1020
21、数组A[0..5,0..6]的每个元素占五个字节,将其按列优先次序存储在起始地址为1000的内存单元中,则元素A[5,5]的地址是(     )。
A、1175           B、1180           C、1205           D、1210
22、二维数组A的每个元素是由6个字符组成的串,其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储,元素A[8,5]的起始地址与当A按列先存储时的元素(    )的起始地址相同。设每个字符占一个字节。
A、A[8,5]         B、A[3,10]           C、A[5,8]         D、A[0,9]
23、A[N,N]是对称矩阵,将下面三角(包括对角线)以行序存储到一维数组T[N(N+1)/2]中,则对任一上三角元素a[i][j]对应T[k]的下标k是(    )。
A、i(i-1)/2+j    B、j(j-1)/2+i     C、i(j-i)/2+1     D、j(i-1)/2+1
24、有一个10090的稀疏矩阵,非0元素有10个,设每个整型数占2字节,则用三元组表示该矩阵时,所需的字节数是(    )。
A、60             B、66                C、18000             D、33   
25、数组A[0..4,-1..-3,5..7]中含有元素的个数(    )。
A、55            B、45               C、36            D、16
26、已知广义表L=((x,y,z),a,(u,t,w)),从L表中取出原子项t的运算是(    )。
A、head(tail(tail(L)))                                B、tail(head(head(tail(L))))
C、head(tail(head(tail(L))))                D、head(tail(head(tail(tail(L)))))
27、已知广义表LS=((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是(   )。
A、head(tail(LS))                                                B、tail(head(LS))
C、head(tail(head(tail(LS)))                                D、head(tail(tail(head(LS))))
28、广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为(   )。Head(Tail(Head(Tail(Tail(A)))))
A、(g)            B、(d)               C、c              D、d
29. 广义表运算式Tail(((a,b),(c,d)))的操作结果是(    )。
A、(c,d)                        B、c,d                        C、((c,d))                 D、d
30、广义表(a,(b,c),d,e)的表头为(    )。
A、a                B、a,(b,c)                C、(a,(b,c))                 D、(a)
31、设广义表L=((a,b,c)),则L的长度和深度分别为(   )。
A、1和1         B、1和3            C、1和2         D、2和3
32、下面说法不正确的是(   )。
A、广义表的表头总是一个广义表        B、广义表的表尾总是一个广义表
C、广义表难以用顺序存储结构          D、广义表可以是一个多层次的结构
二、填空题:
1、矩阵用一维数组表示时,有行优先顺序和(   )两种实现方法。
2、m行n列矩阵可以看成是长度为(   )的线性表,表中的每个元素是长度为m的线性表。
3、10行20列矩阵若用行优先顺序表来表示,则矩阵中第8行第7列元素是顺序表中的第(   )个元素。
4、10行20列矩阵若用列优先顺序表来表示,则矩阵中第7行第8列元素是顺序表中的第(   )个元素。
5、10阶三对角矩阵若用行优先顺序表来表示,则矩阵中第6行第7列元素是顺序表中的第(   )个元素。
6、用行优先顺序表表示10阶对称矩阵,若存储主对角线上的元素,则顺序表的长度为(   );若不存储主对角线上的元素,则顺序表的长度为(   )。
7、用顺序方法存储三元组线性表,通常有两种实现方法,即(   )。
8、(   )是一种常用的表示三元组线性表的链接存储结构。
9、广义表中的每个元素可以是(   ),也可以是(   )。
10、可以将广义表看成是(   )的推广。
11、广义表通常用(   )方法存储。
12、广义表(((a,b,(),c),d),e,((f),g))的长度是(   ),深度是(   )。
三、判断题:
1. 矩阵每一行的元素个数都是相等的。(   )
2. 矩阵的行数和列数可以不相等。(   )
3. 用一维数组表示矩阵,可以简化对矩阵的存取操作。(   )
4. 矩阵一般用二维数组表示。(   )
5. 对称矩阵的行数和列数一定是相同的。(   )
6. 具有特殊用途的矩阵称为特殊矩阵。(   )
7. 对角矩阵的特点是非零元素只出现在矩阵的两条对角钱上。(   )
8. 在n阶三对角矩阵中,每一列都有3个非零元素。(   )
9. 在n阶三对角矩阵中,每一行都有n个元素。(   )
10.若用列优先顺序表来表示n阶三对角矩阵,则该顺序表的长度为3n。(   )
11.稀疏矩阵的特点是矩阵中元素较少。(   )
12.在表示矩阵的三元组顺序表中,各元素的排列顺序与矩阵元素值的大小有关。(   )
13.十字链表是三元组线性表的一种链接存储结构。(   )
14.非零元素较少的特殊矩阵最好用三元组顺序表或十字链表表示。(   )
15.在按行优先顺序存储的三元组线性表中,各元素的排列顺序只与每个元素的行下标有关,与每个元素的列下标无关。(   )
16.用三元组顺序表表示稀疏矩阵,其优点之一是可以随机访问矩阵中每个非零元素。(   )
17.用一维数组表示特殊矩阵,其目的是为了节省存储空间。(   )
18.矩阵作为一种特殊的线性表,其长度通常不能为零。(   )
19.矩阵用一维数组表示,可以节省存储空间。(   )
20.矩阵作为一种特殊的线性表,其长度通常是固定不变的(   )
21.广义表的长度与广义表中含有多少个原子元素有关。(   )
22.广义表的深度与广义表中含有多少个子表元素有关。(   )
23.在广义表中,每个原子的类型都是相同的。(   )
24.在广义表中,每个子表的结构都是相同的。(   )
25.在广义表中,每个原子必须是单个字符。(   )
26.“空的广义表”是指广义表中不包含原子元素。(   )
27.广义表的长度不小于其中任何一个子表的长度。(   )
28.若用链接方法存储广义表,则所需存储空间大小与广义表的长度成正比。(   )
四、应用题:
1、数组A[1..8,-2..6,0..6]以行为主序存储,设第一个元素的首地址是78,每个元素的长度为4,试求元素A[4,2,3]的存储首地址。
2、假设按低下标优先存储整型数组A(-3:8,3:5,-4:0,0:7)时,第一个元素的字节存储地址是100,每个整数占4个字节,问A(0,4,-2,5)的存储地址是什么?
3、三维数组A[1..10,-2..6,2..8]的每个元素的长度为4个字节,试问该数组要占多少个字节的存储空间?如果数组元素以行优先的顺序存贮,设第一个元素的首地址是100,试求元素A[5,0,7] 的存贮首地址。五、综合题:
1、编写一个过程,对一个n×n矩阵,通过行变换,使其每行元素的平均值按递增顺序排列。2、给定有m个整数的递增有序数组a[1..m]和有n个整数的递减有序数组b[1..n],试写出算法:将数组a和b归并为递增有序数组c[l..m+n]。要求:算法的时间复杂度为O(m+n)) 第六章  树和二叉树
一、选择题:
1. 对于一棵具有n个结点、度为4的树来说,(   )。
A、树的高度至多是n-3                B、树的高度至多是n-4
C、第i层上至多有4(i-1)个结点     D、至少在某一层上正好有4个结点
2、对于一棵具有n个结点、度为4的树来说,树的高度至少是(   )。
A、「log2n」           B、「log(3n-1)」   C、「log(3n+1)」       D、「log(2n+1)」
3、度为4、高度为h的树,(   )。
A、至少有h+3个结点                        B、至多有4-l个结点
C、至多有4 h个结点         D、至少有 h+4个结点
4、用双亲数组表示树,其优点之一是(   )比较方便。
A、找指定结点的双亲        B、找指定结点的孩子
C、找指定结点的兄弟        D、判断某结点是不是树叶
5、用孩子链表表示树,其优点之一是(   )比较方便。
A、判断两个指定结点是不是兄弟    B、找指定结点的双亲
C、判断指定结点在第几层          D、计算指定结点的度数
6、如果用孩子链表来表示树,则(   )。
A、树的高度等于各链表长度的最大值    B、树叶的数目和链表的数目成反比
C、树的度数等于各链表长度的最大值    D、结点的数目等于各链表长度之和
7、如果在表示树的二叉链表中有6个空的左指针域,7个空的右指针域,5个结点左、右指针域都为空,则该树中树叶的个数(   )。
A、有7个    B、有6个    C、有5个       D、不能确定
8、如果用二叉链表来表示一棵具有n(n>1)个结点的树,则在二叉链表中(   )。
A、至多有n-1个非空的右指针域   B、至少有2个空的右指针域
C、至少有2个非空的左指针域     D、至多有n-1个空的右指针域
9、二叉树和度为2的树的相同之处包括(   )。
A、每个结点都有一个或两个孩子结点     B、至少有一个根结点
C、至少有一个度为2的结点             D、每个结点至多只有一个双亲结点
10、“二叉树为空”意味着二叉树(   )。
A、由一些没有赋值的空结点构成    B、根结点没有子树
C、不存在                        D、没有结点
11、在高度为h的完全二叉树中,(   )。
A、度为0的结点都在第h层上     B、第i(1≦i<n)层上的结点都是度为2的结点
C、第i(1≦i<n)层上有2个结点    D、不存在度为1的结点
12、每个结点的度或者为0或者为2的二叉树称为正则二叉树,对于n个结点的正则二叉树来说,它的最大高度是(   )。
A、「logn」  B、(n-1)/2   C、「log(n+1)」  D、(n+1)/2
13、若树中结点的前序序列是abcdef,后序序列是bdecfa,则(   )。
A、结点c有两个孩子                B、树有两个度为0的结点
C、树的高度为5                        D、不能唯一确定该树的结构
14、若树中结点的前序序列是abcdefg,后序序列前面3个结点是bde,则后序序列的后面4个结点有可能是(   )。
A、gcfa           B、gacf           C、afgc           D、cfga
15、若某棵二叉树结点的前序序列和中序序列相同,则该二叉树(   )。
A、只有一个结点              B、每个结点都没有左孩子
C、每个结点都没有右孩子      D、不存在
16、若某棵二叉树结点的后序序列和层次序序列正好相反,则该二叉树(   )。
A、每个结点都没有右孩子     B、不存在度为2的结点
C、每个结点都没有左孩子     D、不存在
17、若某棵二叉树结点的前序序列和后序序列相同,则该二叉树(   )。
A、度为 1                   B、只有一个结点
C、每个结点都没有左孩子     D、每个结点都没有右孩子
18、在一棵高度小于4的二叉树中,若结点的前序序列是abcdef,则结点的中序序列有可能是(   )。
A、dcebaf            B、bcdafe            C、cbdafe            D、fcadbe
19、若二叉树中结点的中序序列是abcdef,则结点的前序序列不可能是(   )。
A、dbacef            B、acbedf            C、efbacd            D、bafdce
20、在一棵高度小于5的二叉树中,若结点的中序序列是abcdef;则结点的后序序列有可能是(   )。
A、bdfeca            B、befdca            C、bdefca            D、fedcba
21、在任何一棵二叉树中,如果结点a有左孩子b、右孩子c,则在结点的前序序列、中序序列、后序序列中,(   )。
A、结点b一定在结点a的前面   B、结点a一定在结点c的前面
C、结点b一定在结点c的前面   D、结点a一定在结点b的前面
22、若二叉树结点的前序序列是abcd,后序序列是dcba,则该二叉树(   )。
A、每个分支结点都没有左孩子   B、每个分支结点都只有一个孩子
C、每个分支结点都没有右孩子   D、高度可能为3
23、如果二叉树中结点的前序序列是…a…b…中序序列是…b…a…则(   )。
A.结点a和结点b分别在某结点的左子树和右子树中
B、结点b在结点a的右子树中
C、结点b在结点a的左子树中
D、结点a和结点b分别在某结点的两棵非空子树中
24.如果在二叉树结点的前序序列、中序序列和后序序列中,结点a、b的位置都是a在前、b在后(即形如…a…b…),则(   )。
A、a、b可能是兄弟        B、a可能是b的双亲
C、a可能是b的孩子       D、不存在这样的二叉树
25、如果二叉树结点的前序序列和中序序列分别是abcdefgh和bcafegdh,则后序序列(   )。
A、一定是cbfgehda      B、可能是cbgefhda
C、不存在              D、有多种可能
26、如果完全二叉树结点的后序序列是abcdefgh,则结点的前序序列(   )。
A、不能唯一确定                        B、是hgfedcba
C、是abdchegf                         D、是hdbacgef
27二叉树若用顺序方法存储,则下列四种运算中的(   )最容易实现。
A、前序遍历二叉树
B、判断两个指定结点是不是在同一层上
C、层次遍历二叉树
D、根据结点的位查找其存储位置
28.对含有n个结点、高度为h的二叉树进行非递归后序遍历,所需栈容量(   )。
A、大于h    B、等于h    C、等于n    D、小于n
29、根据使用频率为五个字符设计的哈夫曼编码不可能是(   )。
A、111,110,10,01,00                B、000,001,010,011,l
C、100,11,10,l,0                        D、001,000,01,11,10
30、用整数1,2,3,4,5作为五个树叶的权值,可构造一棵带权路径长度值为(   )的哈夫曼树。
A、33    B、15   C、34     D、54
二、填空题:
1、在树形结构中,如果某结点(   ),则称该结点为根结点;如果某结点(   ),则称该结点为树叶;如果某棵树(   ),则称该树为度为n的树;如果某棵树(   ),则称该树为高度为n的树。
2、高度为h,度为k的树中至少有(   )个结点,至多有(   )个结点。
3、树的存储方法主要有(   )、(   )和(   )三种。
4、在高度为h(h≧0)的二叉树中至多有(   )个结点,至少有(   )个结点。
5、n个结点的二叉树最大高度是(   ),最小高度是(   )。
6、n个结点的二叉树中如果有m个树叶,则一定有(   )个度为1的结点,(   )个度为2的结点。
7、高度为h的满二叉树中有(   )个结点。
8、高度为h的完全二叉树中至少有(   )个结点,至多有(   )个结点。
9、3个结点可以构成(   )种不同形状的树,可以构成(   )种不同形状的二叉树。
10、若用二叉链表来存储具有m个树叶、n个分支结点的树。则二叉链表中有(   )个左指针域为空的结点,有(   )个右指针域为空的结点。
11、在具有n个结点的二叉链表中共有(   )个空指针域。
12、二叉树的存储方法主要有(   )和(   )两种。
13、在有n个结点的顺序存储的完全二叉树中,若某结点在数组中的下标是i,且i<n/2,则该结点的双亲、左孩子和右孩子在数组中的下标分别是(   )、(   )和(   )。
14、二叉树中结点的前序序列是通过对二叉树进行(   )遍历得到的。
15.在任何一棵二叉树中,若结点a有左孩子b、右孩子c,则在结点的前序序列、中序序列、后序序列中,结点(   )一定在结点(   )前面。
16.根据二叉树的中序序列和(   )序列,可以唯一地确定其逻辑结构。
17.如果二叉树A和B共有相同形式的二叉链表存储结构,则A的(   )序列和B的(   )序列相同。
18.在对二叉树进行非递归前序遍历过程中,需要用(   )来暂存所访问结点的地址。
19.在对二叉树进行层次遍历过程中,需要用(   )来暂存所访问结点的地址。
20.在(   )线索二叉树中。有可能每个结点的右孩子指针域都不为空。
21.在(   )线索二叉树中,有可能每个结点的左孩子指针域都不为空。
22.具有(   )值的二叉树称为哈夫曼树。
23.用整数 1,2, 3, 4, 5作为5个树叶的权值,可以构造出(   )棵最优二叉树,每棵最优二叉树的带权路径长度值都是(   )。
24、具有256个结点的完全二叉树的深度为(   )。
25、已知二叉树有50个叶子结点,则该二叉树的总结点数至少是(   )。
26、8层完全二叉树至少有(   )个结点,拥有100个结点的完全二叉树的最大层数为(   )。
27、有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9,试构造一棵哈夫曼树,则其加权路径长度WPL为(   ),字符c的编码是(   )。
28、如果结点A有 3个兄弟,而且B是A的双亲,则B的度是(   )。
29、高度为8的完全二叉树至少有(   )个叶子结点。
30、已知一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度为3的结点,则该树有(   )个叶子结点。
三、判断题:
1、树形结构中的每个结点都有一个前驱。(   )
2、树形结构中的每个结点至多只有一个前驱。(   )
3、度为k的树中至少有一个度为k的结点。(   )
4、在树形结构中,处于同一层上的各结点之间都存在兄弟关系。(   )
5、度为k的树中,每个结点至多有k-1个兄弟。(   )
6、在用图示法表示树形结构时,每一条边必须画成一样长。(   )
7、如果树中有m个分支结点,n个终端结点,则在表示这棵树的孩子链表中共有m个链表。(   )
8、如果树用双亲数组表示,则判断某个结点是不是其他结点的双亲是很方便的。(   )
9、如果树用双亲数组表示,则判断某个结点是不是其他结点的孩子是很方便的。(   )
10、如果树用左孩子右兄弟链表表示,则找任何一个结点的孩子都是很方便的。(   )
11、如果树用左孩子右兄弟链表表示,则找任何一个结点的兄弟都是很方便的。(   )
12、如果树用二叉链表表示,则某个结点是不是树叶的条件是该结点左、右两个指针域的值都为空。(   )
13、二叉树是度为2的树。(   )
14、度为2的树是二叉树。(   )
15、n(n>2)个结点的二叉树中至少有一个度为2的结点。(   )
16、二叉树中结点之间的相互关系可用二元组来表示。(   )
17、不存在这样的二叉树:它有n个度为0的结点,n-l个度为1的结点,n-2个度为2的结点。(   )
18、在任何一棵完全二叉树中,终端结点或者和分支结点一样多,或者只比分支结点多一个。(   )
19、完全二叉树中的每个结点或者没有孩子或者有2个孩子。(   )
20、在所有高度相同的二叉树中,满二叉树总是含有最多的结点数。(   )
21、满二叉树中不存在度为1的结点。(   )
22、若用顺序方法存储满二叉树,则具有前驱、后继关系的结点将占据相邻的存储单元。(   )
23、n个结点的二叉链表中总是有n+1个空的指针域。(   )
24、n个结点的二叉链表中总是有「n/2」个含有空指针域的结点。(   )
25、当树中结点数多于1个时,不可能根据结点的前序序列和后序序列唯一地确定该树的逻辑结构。(   )
26、当二叉树中结点数多于1个时,不能根据结点的前序和后序序列唯一地确定该二叉树的逻辑结构。(   )
27、只要知道完全二叉树中结点的前序序列,就可以唯一地确定它的逻辑结构。(   )
28、哈夫曼树中不存在度为1的结点。(   )
29、在哈夫曼树中,权值相同的树叶结点都在同一层上。(   )
30、在哈夫曼树中,权值较大的树叶结点一般离根结点较远。(   )
四、应用题:
1、已知完全二叉树的第七层有10个叶子结点,则整个二叉树的结点数最多是多少?2、将下列由三棵树组成的森林转换为二叉树。
3、一棵非空的二叉树其先序序列和后序序列正好相反,画出这棵二叉树的形状。4、用一维数组存放的一棵完全二叉树;ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列。
5、请说明是否存在这样的二叉树,即它可以实现后序线索树进行后序遍历时不使用栈;而对前序线索树进行前序遍历时,又有什么样的二叉树可不使用栈。五、综合题:
1、对于二叉树的链接实现,完成非递归的中序遍历过程。2、已知一棵二叉树的中序序列和后序序列,写一个建立该二叉树的二叉链表存储结构的算法。
3、写出中序线索二叉树的线索化过程(已知二叉树T)。4、试找出分别满足下列条件的所有二叉树。
(1)先序序列和中序序列相同                (2)中序序列和后序序列相同
(3)先序序列和后序序列相同                (4)中序序列与层次遍历序列相同5、设T是一棵二叉树,除叶子结点外,其它结点的度数皆为2,若 T中有6个叶结点,试问:
(1)T树的最大深度Kmax=?最小可能深度Kmin=?
(2)T树中共有多少非叶结点?
(3) 若叶结点的权值分别为1,2,3,4,5,6。请构造一棵哈曼夫树,并计算该哈曼夫树的带权路径长度wpl。
6、一棵有n(n>0)个结点的d度树,若用多重链表表示,树中每个结点都有d个链域,则在表示该树的多重链表中有多少个空链域? 为什么?
7、假设用于通讯的电文仅有8个字母组成,字母在电文中出现的频率分别为:7,19,2,6,32,3,
21,10。试用这8个频率值构成哈夫曼树,并画出该哈夫曼树所对应的森林。第七章  图
一、选择题:
1. 对图7.l所示的无向图,从顶点V1开始进行深度遍历,可得到顶点访问序列(    )。
A.1  2  4  3  5  7  6            
B.1  2  4  3  5  6  7         
C.1  2  4  5  6  3  7
D.1  2  3  4  5  7  62.对图7.1所示的无向图,从顶点V1开始进行广度遍历,可得到顶点访问序列(    )
A.1  3  2  4  5  6  7
B.1  2  4  3  5  6  7
C.1  2  3  4  5  7  6
D.2  5  1  4  7  3  63.在图7.2所示的有向图中,存在一个强连通分量GZ(V,E),其中,(    )。
A.V={V2,V3,V5,V6}
   E={<V5,V2>,<V2,V3>,<V2,V6>,<V6,V3>,<V3,V5>}
B.V={V2,V3,V5,V6}
   E={<V5,V2>,<V2,V6>,<V6,V3>,<V3,V5>}
C.V={V2,V3,V5}
   E={<V2,V3>,<V3,V5>,<V5,V2>}
D.V={V1,V7}
   E={<V1,V7>,<V7,V1>}
4.对图7.2所示有向图,从顶点V3开始进行广度遍历,可得到一个广度优先生成树,它所包含的边是(    )。
A.<V1,V7>,<V2,V6>,<V3,V5>,<V5,V1>,<V5,V2>,<V5,V4>
B.<V1,V3>,<V3,V4>,<V3,V5>,<V4,V7>,<V5,V1>,<V6,V3>
C.<V2,V6>,<V3,V4>,<V3,V5>,<V4,V7>,<V5,V2>,<V7,V1>
D.<V2,V6>,<V3,V4>,<V3,V5>,<V4,V7>,<V5,V1>,<V5,V2>
5、一个n个顶点的连通无向图,其边的个数至少为(    )。
A、n-1                B、n                C、n+1                        D、nlogn
6、关键路径是事件结点网络中(    )。
A、从源点到汇点的最长路径        B、从源点到汇点的最短路径
C、最长回路                      D、最短回路
7、下面哪一方法可以判断出一个有向图是否有环(    )。
A、深度优先遍历   B、拓扑排序   C、求最短路径  D、求关键路径
8、在有向图G的拓扑序列中,若顶点Vi在顶点Vj之前,则下列情形不可能出现的是(    )。  
A、G中有弧<Vi,Vj>             B、G中有一条从Vi到Vj的路径            
C、G中没有弧<Vi,Vj>            D、G中有一条从Vj到Vi的路径
9、下列哪一种图的邻接矩阵是对称矩阵?(    )。
A、有向图            B、无向图           C、AOV网          D、AOE网
10、一般情况下,图的DFS生成树的高度与BFS生成树的高度的关系是(    )。
A、小于 ?     B、等于       C、大于       D、小于或等于
11.图中有关路径的定义是(    )。
A、由顶点和相邻顶点序偶构成的边所形成的序列      B、由不同顶点所形成的序列
C、由不同边所形成的序列                          D、上述定义都不是
12.设无向图的顶点个数为n,则该图最多有(  )条边。
A、n-1                        B、n(n-1)/2                C、 n(n+1)/2                D、0
13、要连通具有n个顶点的有向图,至少需要(    )条边。
A、n-l                        B、n                         C、n+l                        D、2n
14、n个结点的完全有向图含有边的数目(   )。
A、nn        B、n(n+1)     C、n/2            D、n(n-l)
15、一个有n个结点的图,最少有(    )个连通分量,最多有(    )个连通分量。
A、0           B、1                                C、n-1             D、n
16、在一个无向图中,所有顶点的度数之和等于所有边数(    )倍,在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的(    )倍。
A、1/2          B、2             C、1               D、4
17、用DFS遍历一个无环有向图,并在DFS算法退栈返回时打印相应的顶点,则输出的顶点序列是(  )。
A、逆拓扑有序         B、拓扑有序            C、无序的
18、下列说法不正确的是(    )。
A、图的遍历是从给定的源点出发每一个顶点仅被访问一次   C、图的深度遍历不适用于有向图
B、遍历的基本算法有两种:深度遍历和广度遍历           D、图的深度遍历是一个递归过程
19、下面哪一方法可以判断出一个有向图是否有环(回路):(   )。
A、深度优先遍历   B、拓扑排序   C、求最短路径  D、求关键路径
20、下面关于求关键路径的说法不正确的是(    )。
A、求关键路径是以拓扑排序为基础的
B、一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C、一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D、关键活动一定位于关键路径上
二、填空题:
1、判断一个无向图是一棵树的条件是(    )。
2、有向图G的强连通分量是指(    )。
3、一个连通图的(    )是一个极小连通子图。
4、具有10个顶点的无向图,边的总数最多为(    )。
5、若用n表示图中顶点数目,则有(    )条边的无向图成为完全图。
6、G是一个非连通无向图,共有28条边,则该图至少有(    )个顶点。
7、在有n个顶点的有向图中,若要使任意两点间可以互相到达,则至少需要(    )条弧。
8、在有n个顶点的有向图中,每个顶点的度最大可达(    )。
9、设G为具有N个顶点的无向连通图,则G中至少有(    )边。
10、n个顶点的连通无向图,其边的条数至少为(    )。
11、如果含n个顶点的图形形成一个环,则它有(    )棵生成树。
12、N个顶点的连通图的生成树含有(    )条边。
13、构造n个结点的强连通图,至少有(    )条弧。
14、有N个顶点的有向图,至少需要量(    )条弧
才能保证是连通的。
15、右图中的强连通分量的个数为(    )个。
16、N个顶点的连通图用邻接矩阵表示时,该矩阵
至少有(    )个非零元素。
17、在图G的邻接表表示中,每个顶点邻接表中所含的结点数,对于无向图来说等于该顶点的(    );对于有向图来说等于该顶点的(    )。
18、在有向图的邻接矩阵表示中,计算第I个顶点入度的方法是(    )。
19、对于一个具有n个顶点e条边的无向图的邻接表的表示,则表头向量大小为(    ),邻接表的边结点个数为(    )。
20、在AOE网中,从源点到汇点路径上各活动时间总和最长的路径称为(    )。三、判断题:
1、树中的结点和图中的顶点就是指数据结构中的数据元素。(    )
2、在n个结点的无向图中,若边数大于n-1,则该图必是连通图。(   )
3、有e条边的无向图,在邻接表中有e个结点。(    )
4、有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。(   )
5、强连通图的各顶点间均可达。(    )
6、强连通分量是无向图的极大强连通子图。(    )
7、连通分量指的是有向图中的极大连通子图。(    )
8、邻接多重表是无向图和有向图的链式存储结构。(    )
9、 十字链表是无向图的一种存储结构。(    )
10、无向图的邻接矩阵可用一维数组存储。(    )
11、用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。(    )
12、有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。(    )
13、有向图的邻接矩阵是对称的。(    )【
14、无向图的邻接矩阵一定是对称矩阵,有向图的邻接矩阵一定是非对称矩阵。(    )
15、一个有向图的邻接表和逆邻接表中结点的个数可能不等。(    )
16、需要借助于一个队列来实现DFS算法。(    )
17、广度遍历生成树描述了从起点到各顶点的最短路径。(    )
18、任何无向图都存在生成树。(    )
19、不同的求最小生成树的方法最后得到的生成树是相同的.(    )
20、带权无向图的最小生成树必是唯一的。(    )
21、最小代价生成树是唯一的。(    )
22、一个网(带权图)都有唯一的最小生成树。(    )
23、带权的连通无向图的最小代价生成树是唯一的。(    )
24、最小生成树问题是构造连通网的最小代价生成树。(    )
25、拓扑排序算法把一个无向图中的顶点排成一个有序序列。(  )
26、拓扑排序算法仅能适用于有向无环图。(    )
27、无环有向图才能进行拓扑排序。(    )
28、有环图也能进行拓扑排序。(    )
29、拓扑排序的有向图中,最多存在一条环路。(    )
30、任何有向图的结点都可以排成拓扑排序,而且拓扑序列不唯一。(    )
31、既使有向无环图的拓扑序列唯一,也不能唯一确定该图。(    )
32、若一个有向图的邻接矩阵对角线以下元素均为零,则该图的拓扑有序序列必定存在。(    )
33、AOV网的含义是以边表示活动的网。(    )
34、对一个AOV网,从源点到终点的路径最长的路径称作关键路径。
35、关键路径是AOE网中从源点到终点的最长路径。(    )
36、AOE网一定是有向无环图。(    )
37、在表示某工程的AOE网中,加速其关键路径上的任意关键活动均可缩短整个工程的完成时间。(    )
38、在AOE图中,关键路径上某个活动的时间缩短,整个工程的时间也就必定缩短。(    )
39、在AOE图中,关键路径上活动的时间延长多少,整个工程的时间也就随之延长多少。(    )
40、当改变网上某一关键路径上任一关键活动后,必将产生不同的关键路径。(   )
四、应用题:
1、对一个图进行遍历可以得到不同的遍历序列,那么导致得到的遍历序列不唯一的因素有哪些?
2、已知AOV-网如下图所示:给出该有向图(至少两组)拓扑有序序列,并简述如何进行拓扑排序?            
              
五、综合题:
1、根据下图求出其最小生成树。(注:任选一种算法,要求有具体实现步骤)。
              
2、什么是AOE网?求出下图所示AOE网中的关键路径(要求表明每一个顶点的最早发生时间和最迟发生时间,并画出关键路经)。
3、设无向图G有n个点e条边,写一算法建立G的邻接多表,要求该算法时间复杂性为O(n+e),且除邻接多表本身所占空间之外只用O(1)辅助空间。4、试编写求无向图G的连通分量的算法。要求输出每一连通分量的顶点值。(设图G已用邻接表存储)第九章  查找
一、选择题:
1、在二叉排序树中,凡是新插入的结点,都是没有(    )的。
A、孩子    B、关键字   C、平衡因子  D、赋值
2、在平衡二叉排序树中;每个结点(    )。
A、左子树结点个数和右子树结点个数相差不超过1
B、平衡因子为0
C、左子树度数和右子树度数相差不超过1
D、左子树高度和右子树高度相差不超过1
3、含有27个关键字的平衡二叉排序树(    )。
A、有13个度为2的结点    B、最大高度是6
C、最低高度是6            D、有14个度为0的结点
4、只有在顺序存储结构上才能实现的查找方法是(    )法。
A、顺序查找   B、折半查找   C、树型查找    D、散列查找
5、在14个元素中查找某个元素,如果已知在坏情况下要进行5次元素间的比较,则可以断定所采用的查找方法可能是(    )法。
A、顺序查找   B、折半查找   C、树型查找    D、分块查找
6、含12个结点的平衡二叉排序树,其最大深度是(    )。
A、4     B、5   C、6     D、12
7、主关键字是指(    )。
A、数据结构中最重要的数据元素
B、数据元素中最重要的数据项
C、数据元素中取值惟一的数据项
D、其值能惟一标志一个数据元素的数据项
8、在数据元素较多而且固定不变的情况下,宜采用(    )法。
A、折半查找           B、分块查找       C、二叉排序树查找     D、顺序查找
9、有序表( 2,4,6,8,10,12,14,16,18,20)上用折半查找方法查找元素14,依次被比较的元素是(    )。
A、10,16,12,14   B、10,16,14    C、12,16,14   D、12,18,14
10、含有15个元素的有序表上,用折半查找方法查找一个表中不存在的元素,需要进行(    )次元素间的比较。
A、0      B、4    C、5    D、15
11、在有序表( 2,4,6,8,10,12,14,16,18,20)上用折半查找方法查找元素11,需要进行(    )次元素的比较。
A、3      B、4    C、5    D、10
12、在有序表( 2,4,6,8,10,12,14,16,18,20)上用折半查找方法查找元素9依次被比较的元素是(    )。
A、2,4,6,8,10    B、10,4,6,8     C、10,6,8          D、12,6,8,10
13、在散列查找过程中,可用(    )来处理冲突。
A、除留余数法       B、数字分析法    C、线性探测法       D、关键字比较法
14、用折半查找方法查找某个元素,依次被比较的元素有可能是(    )。
A、77,38,66,15,49        B、77,49,66,38,15
C、15,66,3 8,49,77        D、15,77,38,49,66
15、在顺序查找、折半查找、分块查找、树型查找这4种查找方法中,一般情况下,时间复杂度相同的是(    )。
A、折半查找和树型查找     B、顺序查找和树型查找
C、分块查找和树型查找     D、折半查找和分块查找                                                                                                                                       
16、在顺序查找、折半查找、分块查找、构型查找这4种查找方法中,最坏情况下,时间复杂度相同的是(    )。
A、折半查找和树型查找     B、顺序查找和树型查找
C、分块查找和树型查找     D、折半查找和分块查找
17、在顺序查找、折半查找、分块查找、平衡二叉排序树查找这4种查找方法中,在最坏情况下,时间复杂度相同的是(    )。
A、折半查找和平衡二叉排序树查找   B、顺序查找和平衡二叉排序树查找
C、顺序查找和折半查找             D、分块查找和平衡二叉排序树查找
18、如果在100个元素中查找其中任何一个元素,最多只需比较 5次,则所用的查找方法有可能是(    )。
A、散列查找    B、折半查找   C、分块查找   D、树型查找
19、如果在n个元素中查找其中任何一个元素至少要比较2次,则所用的查找方法有可能是(    )。
A、折半查找    B、分块查找   C、树型查找   D、散列查找
20、若查找每个记录的概率均等,则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录,其平均查找长度ASL为(   )。
A、(n-1)/2       B、n/2        C、(n+1)/2        D、n
二、填空题:
1、可以唯一标志一个数据元素的关键字称为(   ),可以标志多个数据元素的关键字称为(   )。
2、衡量查找算法性能好坏的主要标准是(   )。
3、顺序查找方法的缺点是(   )。
4、为了实现折半查找,线性表必须采用(   )方法存储。
5、折半查找方法的优点是(   )。
6、和顺序查找方法相比,折半查找方法的主要缺点是(   )。
7、为了实现分块查找,线性表必须采用(   )方法存储。
8、对二叉排序树进行(   )遍历,可以得到接关键字从小到大排列的结点序列。
9、在高度为h含n个结点的二叉排序树上查找一个关键字至多比较次数为(   )。
10、在平衡二叉排序树中,每个结点的平衡因子等于(   )。
11、二叉排序树的排序性质是指(   )。
12、平衡二叉排序树的平衡性质是指(   )。
13、采用散列存储方法时,用于计算结点存储地址的是(   )。
14、在散列存储结构中,散列地址空间是指(   )。
15、在有序表(k,k,…,k)上用折半查找方法查找99次,其中,至少有一个关键字被比较了99次,这个关键字是(   )。
16、将有序表(k,k,…,k)中的关键字依次插人到一棵原来为空的二叉排序树中,这棵二叉排序树的高度是(   )。
17、在各元素查找概率相等的情况下,用顺序查找方法从含有12个元素的有序表中查找一个元素,元素间的平均比较次数是(   )。
18、在有序表A[1..12]中,采用二分查找算法查等于A[12]的元素,所比较的元素下标依次为(   )。
19、对于长度为255的表,采用分块查找,每块的最佳长度为(   )。
20、己知有序表为(12,18,24,35,47,50,62,83,90,115,134)当用二分法查找90时,需(   )次查找成功,47时(   )成功,查100时,需(   )次才能确定不成功。
三、判断题:
1、关键字是一个数据元素。(   )
2、查找是否成功的关键在于是否按主关键字查找。(   )
3、顺序查找方法只能在顺序存储结构上进行。(   )
4、顺序查找是一种在有序的线性表上进行的查找方法。(   )
5、折半查找可以在有序的双向链表上进行。(   )
6、分块查找的效率与线性表被分成多少块有关。(   )
7、二叉排序树是用来进行排序的。(   )
8、在二叉排序树中,每个结点的关键字都比左孩子关键字大,比右孩子关键字小。(   )
9、每个结点的关键字都比左孩子关键字大,比右孩子关键字小,这样的二叉树都是二叉排序树。(   )
10、二叉排序树的查找效率和二叉排序树的高度有关。(   )
11、二叉排序树的高度和构造二叉排序树时结点的插人顺序无关。(   )
12、在平衡二叉排序树中,每个结点的平衡因子值是相等的。(   )
13、在平衡二叉排序树中,以每个分支结点为根的子树都是平衡的。(   )
14、在散列查找中不涉及关键字的比较。(   )
15、散列存储法只能存储数据元素的值,不能存储数据元素之间的关系。(   )
16、散列冲突是指同一个关键字对应多个不同的散列地址。(   )
17、散列表的负载因子和关键字的大小无关。(   )
18、散列表的负载因子和散列地址空间大小成正比。(   )
19、分块查找过程是首先在索引表上查找,然后再到结点表中查找。(   )
20、为实现分块查找,必须用索引存储方法存储线性表。(   )
21、在含有n个结点的二叉排序树上查找一个关键字,至多比较「logn」次。(   )
22、散列表的负载因子等于存人散列表中的结点个数。(   )
23、由n个结点构成的平衡二叉排序树,其最大高度是n。(   )
24、由n个结点构成的二叉排序树,其最低高度是「log(n+1)」。(   )
25、散列查找过程中,关键字的比较次数和散列表中关键字的个数直接相关。(   )
26、在散列存储过程中发生“冲突”是由于存储空间太小的缘故。(   )
27、在用拉链法处理冲突的散列表中,散列函数值相同的关键字总是在同一个链表中。(   )
28、含有n个关键字的二叉排序树,其高度等于最大关键字或最小关键字所在的层数。(   )
29、高度越低,二叉排序树的查找性能越好。(   )
30、在二叉排序树中,新插入的关键字总是处于最底层。(   )
四、应用题:
1、用分块查找法,有2000项的表分成多少块最理想?每块的理想长度是多少?若每块长度为25 ,平均查找长度是多少?2、设有n个值不同的元素存于顺序结构中,试问:你能否用比(2n-3)少的比较次数选出这n个元素中的最大值和最小值?若能,请说明是如何实现的;在最坏情况下,至少要进行多少次比较。五、综合题:
1、写出在二叉排序树中删除一个结点的算法,使删除后仍为二叉排序树。设删除结点由指针p所指,其双亲结点由指针f所指,并假设被删除结点是其双亲结点的右孩子。
2、假设一棵平衡二叉树的每个结点都标明了平衡因子b,试设计一个算法,求平衡二叉树的高度。
3、编写对有序表进行顺序查找的算法,并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值,又查找成功和不成功的概率也相等,试求进行每一次查找时和给定值进行比较的关键字个数的期望值。第十章  内部排序
一、选择题:
1、如果(   ),则称这种排序方法是不稳定的。
A、排序前后,排序码相同的元素在线性表中的相对位置可能会被颠倒
B、排序前后,排序码相同的元素在线性表中的相对位置一定会被颠倒
C、对同一个线性表。每次排序的结果可能不相同
D、排序结果不可预测
2、如果元素有相同的排序码,并且在进行简单选择排序前,R1在R2的前面,则在排序结束后,(   )。
A、R1一定在R2的前面     B、R1有可能在R2的前面
C、R1一定在R2的后面     D、选择R1或R2中的一个留在线性表中
3、如果元素R1和R2有相同的排序码,并且在进行直接插入排序前,R1在R2的前面,则当排序结束后,(   )。
A、R1一定在R2的前面      B、R1一定在R2的后面
C、R1有可能在R2的前面    D、选择R1或R2中的一个留在线性表中
4、在线性表中各元素已经有序排列的情况下,执行(   )排序,可以尽快结束排序过程。
A、起泡   B、堆    C、基数      D、快速
5、在线性表中各元素已经有序排列的情况下,执行(   )排序,最费时间。
A、起泡   B、直接插入   C、折半插入   D、简单选择
6、在线性表中各元素已经有序排列的情况下,执行(   )排序,排序码比较次数最少。
A、快速   B、折半插入   C、直接插入   D、归并
7、在线性表中各元素已经有序排列的情况下,执行(   )排序,排序码比较次数最少。
A、折半插入   B、简单选择   C、归并   D、快速
8、在线性表中各元素已经有序排列的情况下,执行(   )排序,排序码比较次数最多。
A、归并   B、直接选择   C、拆半插入   D、基数
9、在线性表中各元素已经有序排列的情况下,执行(   )排序,元素移动次数最少。
A、快速   B、归并   C、堆    D、简单选择
10、下面 4个序列中,只有(   )满足堆的定义。
A、97,76,85,49,76,38,27,13    B、97,13,85,76,49,27,38,76
C、97,85,38,27,76,49,76,13    D、97,85,38,76,76,49,27,13
11、在线性表中各元素逆序排列的情况下,执行(   )排序,元素的移动次数最少。
A、起泡   B、直接插入    C、简单选择   D、折半插入
12、在线性表中各元素逆序排列的情况下,执行(   )排序,排序码比较次数最少。
A、起泡   B、直接插入    C、折半插入     D、简单选择
13、假设线性表中元素很多,而且在交换第一个元素和最后一个元素后,线性表即成有序表。在这种情况下,执行(   )排序,排序码比较次数最少。
A、直接插入   B、起泡   C、简单选择   D、归并
14、假设排序过程中线性表的变化情况如下:
21,25,49,25,16,8(初始状态)
21,25,49,25,16,8
21,25,49,25,16,8
21,25,25,49,16,8
16,21,25,25,49,8
8,16,21,25,25,49(最终状态)
可以断定,所采用的排序方法是(   )排序。
A、归并   B、起泡    C、简单选择     D、直接插入
15、假设排序过程中线性表的变化情况如下:
21,25,49,25,16,8(初始状态)
8,21,25,49,25,16
8,16,21,25,49,25
8,16,21,25,25,49
8,16,21,25,25,49(最终状态)
可以断定,所采用的排序方法是(   )排序。
A、起泡   B、直接插入     C、简单选择     D、归并
16、假设排序过程中线性表的变化情况如下:
21,25,49,25,16,8(初始状态)
8,25,49,25,16,21
8,16,49,25,25,21
8,16,21,25,25,49
8,16,21,25,25,49
8,16,21,25,25,49(最终状态)
可以断定,所采用的排序方法是(   )排序。
A、直接插入   B、简单选择     C、起泡    D、归并
17、假设排序过程中线性表的变化情况如下:
21,25,49,25,16,8(初始状态)
21,25,25,49,8,16
21,25,25,49,8,16
8,16,21,25,25,49(最终状态)
可以断定,所采用的排序方法是(   )排序。
A、起泡   B、直接插入   C、归并   D、简单选择
18、假设排序过程中线性表的变化情况如下:
   21,25,49,25,16,8(初始状态)
   21,25,25,16,8,49
   21,25,16,8,25,49
   21,16,8,25,25,49
   16,8,21,25,25,49
   8,16,21,25,25,49(最终状态)
可以断定,所采用的排序方法是(   )排序。
A、起泡   B、归并   C、堆   D、快速
19、假设排序过程中线性表的变化情况如下:
    21,25,49,25,16,8(初始状态)
    8,16,21,25,49,25
    8,16,21,25,25,49
    8,16,21,25,25,49(最终状态)
可以断定,所采用的排序方法是(   )排序。
A、快速   B、堆   C、起泡    D、简单选择
20、假设线性表原始状态为
    2,1,4,3,6,5,8,7,10,9
欲使排序码比较次数最少,应采用(   )排序法。
A、起泡   B、直接插入   C、归并    D、折半插入
21、假设线性表原始状态为:
    l,2,3,4,5,10,6,7,8,9
欲使排序码比较次数最少,应采用(   )排序法。
A、起泡  B、快速    C、归并   D、折半插入
22、下面4个原始的线性表中都有相同的排序码,在对线性表(   )执行简单选择排序后,那两个相同排序码在表中的相对次序不会改变。
A、1,3,4,2,3,5      B、l,5,5,3,4,2
C、2,1,4,5,4,3      D、2,4,5,3,2,1
23.下面4个原始的线性表中都有相同的排序码,在对线性表(   )执行简单选择排序后,那两个相同排序码在表中的相对次序将被颠倒。
A、3,5,4,5,2,1    B、l,3,4,2,3,5
C、2,1,4,5,4,3    D、4,4,3,5,1,2
24、下面4个原始的线性表中都有相同的排序码,对线性表(   )执行快速排序后,那两个相同排序码在表中的相对次序不会改变。
A、1,4,3,4,2,5    B、l,2,2,3,4,5
C、5,4,2,3,l,1    D、5,5,2,4,3,l
25、对下面4个线性表分别进行快速排序,其中对(   )的排序速度最快。
A、1,l,3,4,5,6,7,8    B、4,1,3,2,6,5,7,8
C、4,3,2,1,6,5,7,8    D、4,2,3,l,5,6,7,8
26、按排序码从小到大的顺序对线性表进行堆排序时,若表中元素的初始排列为(   ),则在建初始堆时,元素移动次数最少。
A、8,6,7,5,1,2,3,4    B、8,6,5,7,4,3,2,1
C、8,5,7,6,4,2,3,1    D、8,5,6,7,1,2,3,4
27、排序过程中,元素的移动次数与各元素原始的排列顺序无关的排序方法是(   )排序。
A、简单选择   B、快速   C、堆    D、归并
28、比较次数与排序的初始状态无关的排序方法是(    )。
A、直接插入排序       B、起泡排序      C、快速排序       D、简单选择排序
29、下列排序算法中(   )排序在一趟结束后不一定能选出一个元素放在其最终位置上。
A、选择                        B、冒泡                                C、归并                        D、堆
30、就平均性能而言,目前最好的内排序方法是(   )排序法。
A、冒泡                        B、希尔插入                        C、交换                        D、快速 二、填空题:
1. 对n个元素进行直接插人排序,排序码的比较次数至少是(   )次。
2. 对n个元素进行起泡排序,排序码的比较次数至少是(   )次。
3. 对n个元素进行简单选择排序,元素的移动次数至多是(   )次。
4. 对n个元素进行基数排序,元素的移动次数是(   )次。
5. 若线性表中有x个元素,排序码是长度为y的字母串,则进行基数排序时,共需进行(   )趟的分配与收集。
6. 若采用堆排序法对线性表中的元素进行从大到小的排序,则所建的堆中,堆顶元素的排序码一定是(   )。
7. 在对线性表进行归并排序时,线性表中各元素原始的排列顺序不会影响到(   )次数。
8. 若线性表中有n个元素,则快速排序的平均执行时间用数量级表示是(   )。
9. 若线性表中有n个元素,则在最坏的情况下,堆顺序的执行时间用数量级表示是(   )。
10.若线性表中有n个元素,则在最坏的情况下,快速排序的执行时间用数量级表示
是(   )。
11.对n个元素进行快速排序,所需的辅助存储空间用数量级表示是(   )。
12.对n个元素进行归并排序,所需的辅助存储空间用数量级表示是(   )。
13.对n个元素进行堆排序,所需的辅助存储空间用数量级表示是(   )。
14.排序算法的执行时间一般用排序过程中(   )来衡量。
15.在排序过程中,任何情况下都不比较排序码大小的排序方法是(   )。
16.为长度为5的顺序表建初始堆,排序码的比较次数至少是(   )次,至多是(   )次。
17.为长度为5的顺序表建初始堆,元素的移动次数至多是(   )次。
18.对n个元素执行快速排序,在进行第一次分组时,元素的移动次数至多是(   )次。
19.在归并两个长度为m的有序表时,排序码的比较次数至少是(   )次,至多是(   )次。
20.与直接插入排序方法相比,折半插入排序方法减少了排序过程中的(   )。
三、判断题:
1、在起泡排序过程中,排序码较小的元素总是向前移动,排序码较大的元素总是向后移动。(   )
2、只有在线性表的初始状态为逆序排列的情况下,起泡排序过程中,元素的移动次数才会达到最大值。(   )
3、只有在线性表的初始状态为逆序排列的情况下,起泡排序过程中,排序码的比较次数才会达到最大值。(   )
4、只有在线性表的初始状态为逆序排列的情况下,简单选择排序过程中,元素的移动次数才会达到最大值。(   )
5、对n个元素执行简单选择排序,排序码的比较次数总是n(n-1)/2次。(   )
6、只有在线性表的初始状态为逆序排列的情况下,直接插人排序过程中,元素的移动次数才会达到最大值。(   )
7、只有在线性表的初始状态为顺序排列的情况下,快速排序过程中,排序码的比较次数才会达到最大值。(   )
8、只有在线性表的初始状态为顺序排列或逆序排列的情况下,快速排序过程中,排序码的比较次数才会达到最大值。(   )
9、对n个元素执行快速排序,在进行第一次分组时,排序码的比较次数总是n-l次。(   )
10、对n个元素执行快速排序,如果每次分组时,元素的移动次数都是最少的,则快速排序的执行时间达到最小值O(nlog2n)。(   )
四、应用题:
1、在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动,从而认为该排序算法是不稳定的,这种说法对吗?为什么?
2、设有5个互不相同的元素a、b、c、d、e,能否通过7次比较就将其排好序?如果能,请列出其比较过程;如果不能,则说明原因。
3、以下概念的区别:拓扑排序与冒泡排序。
4、快排序、堆排序、合并排序、Shell排序中哪种排序平均比较次数最少,哪种排序占用空间最多,哪几种排序算法是不稳定的?  
5、全国有10000人参加物理竞赛,只录取成绩优异的前10名,并将他们从高分到低分输出。而对落选的其他考生,不需排出名次,问此种情况下,用何种排序方法速度最快?为什么?
五、综合题:
1、输入50个学生的记录(每个学生的记录包括学号和成绩),组成记录数组,然后按成绩由高到低的次序输出(每行10个记录)。排序方法采用选择排序。2、设有一个数组中存放了一个无序的关键序列K1、K2、…、Kn。现要求将Kn放在将元素排序后的正确位置上,试编写实现该功能的算法,要求比较关键字的次数不超过n。
3、借助于快速排序的算法思想,在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..h]中。若查找成功,则输出该记录在r数组中的位置及其值,否则显示“not find”信息。请编写出算法并简要说明算法思想。
www.ap5u.com提醒:答案可以联系Q或微信 761296021
快速回复 返回顶部 返回列表