数据结构第四章习题答案
8．请用SQL的GRANT 和REVOKE语句(加上视图机制)完成以下授权定义或存取控制功能:
( a ）用户王明对两个表有SELECT 权力。
GRANT SELECT ON 职工,部门
TO 王明
( b ）用户李勇对两个表有INSERT 和DELETE 权力。
GRANT INSERT,DELETE ON 职工,部门
TO 李勇
( c ) 每个职工只对自己的记录有SELECT 权力。
GRANT SELECT ON 职工
WHEN USER()=NAME
TO ALL;
( d ）用户刘星对职工表有SELECT 权力，对工资字段具有更新权力。
GRANT SELECT,UPDATE(工资) ON 职工
TO 刘星
( e ）用户张新具有修改这两个表的结构的权力。
GRANT ALTER TABLE ON 职工,部门
TO 张新;
( f ）用户周平具有对两个表所有权力（读，插，改，删数据），并具有给其他用户授权的权力。
GRANT ALL PRIVILIGES ON 职工,部门
TO 周平
WITH GRANT OPTION;
( g ）用户杨兰具有从每个部门职工中SELECT 最高工资、最低工资、平均工资的权力，他不能查看每个人的工资。
CREATE VIEW 部门工资AS
SELECT 部门.名称,MAX(工资),MIN(工资),AVG(工资)
FROM 职工,部门
WHERE 职工.部门号=部门.部门号
GROUP BY 职工.部门号
GRANT SELECT ON 部门工资
TO 杨兰;
9 ．把习题8 中（1）---（7）的每一种情况，撤销各用户所授予的权力
(1) REVOKE SELECT ON 职工，部门FROM 王明；
(2) REVOKE INSERT , DELETE ON 职工，部门FROM 李勇；
(3) REOVKE SELECT ON 职工
WHEN USER ( ) =NAME
FROM ALI ;
(4) REVOKE SELECT , UPDATE ON 职工
FROM 刘星；
(5) REVOKE ALTER TABLE ON 职工，部门
FROM 张新；
(6) REVOKE ALL PRIVILIGES ON 职工，部门
FROM 周平；
(7) REVOKE SELECT ON 部门工资FROM 杨兰；
DROP VIEW 部门工资；
经典数据结构面试题(含答案)
栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是 __________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 ____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________
数据结构习题(,,章)
数据结构习题(,,章)
————————————————————————————————作者：————————————————————————————————日期：
第四章串 一．选择题 1．若串S='software',其子串的数目是（） A．8 B．37 C．36 D．9 2．设有两个串p和q,求q在p中首次出现的位置的运算称作（） A．连接B．模式匹配C．求串长D．求子串 3．设字符串S1=“ABCDEFG”，S2=“PQRST”，则运算： S=CONCAT（SUBSTR（S1，2，LEN（S2））；SUBSTR（S1，LEN（S2），2））；后的串值为（） A．A BCDEF B．BCDEFG C．BCDPQRST D． BCDEFEF 4．下面的说法中，只有（）是正确的 A．串是一种特殊的线性表B．串的长度必须大于零 C．串中元素只能是字母D．空串就是空白串 5．两个字符串相等的条件是（） A．两串的长度相等 B．两串包含的字符相同 C．两串的长度相等，并且两串包含的字符相同 D．两串的长度相等，并且对应位置上的字符相同 二．填空题 1．串“ababcbaababd”的next函数值为，nextval函数值为。2．子串的长度为。 第五章数组和广义表 一．选择题 1．设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( ) A. BA+141 B. BA+180 C. BA+222 D. BA+225 2．假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（） A. 808 B. 818 C. 1010 D. 1020 3．对稀疏矩阵进行压缩存储目的是（） A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度 4．假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（）
数据结构模拟卷(含答案)经典习题培训讲学
数据结构模拟卷(含答案)经典习题
练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4
6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( )
数据结构课后习题答案第四章
第四章 一、简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。 答： ●空串是指不包含任何字符的串，它的长度为零。 空白串是指包含一个或多个空格的串，空格也是字符。 ●串常量是指在程序中只可引用但不可改变其值的串。 串变量是可以在运行中改变其值的。 ●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。 ●静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。 动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。 ●目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。 ●有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位移，每一次合法位移后如果模式串与目标中相应的字符相同，则这次位移就是有效位移(也就是从此位置开始的匹配成功)，反之，若有不相同的字符存在，则此次位移就是无效位移(也就是从此位置开始的匹配失败)。 二、假设有如下的串说明： char s1[30]="Stocktom,CA", s2[30]="March 5 1999", s3[30], *p; (1)在执行如下的每个语句后p的值是什么? p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6'); (2)在执行下列语句后，s3的值是什么? strcpy(s3,s1); strcat(s3,","); strcat(s3,s2); (3)调用函数strcmp(s1,s2)的返回值是什么?
数据结构模拟卷(含答案)经典习题
练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 1
6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位 10. 下列图示的顺序存储结构表示的二叉树是( ) 2
数据结构复习题三
数据结构练习题 第一章绪论 一．选择题 1、在数据结构的讨论中把数据结构从逻辑上分为（）。 A.内部结构与外部结构 B.静态结构与动态结构 C.线性结构与非线性结构 D.紧凑结构与非紧凑结构 2、采用线性链表表示一个向量时，要求占用的存储空间地址（）。A: 必须是连续的 B 部分地址必须是连续的 C: 一定是不连续的C: 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（）。 A: n B: n/2 C: (n-1)/2 D: (n+1)/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（）。 A: s→next = p→next;p→next = s; B: p→next= s; s→next = q; C: p→next = s→next;s→next = p;D: q→next= s;s→next= p; 8.下面程序段的时间复杂度为____________。 for(int i=0; i 二．填空题 1.通常，评价一个算法有正确性、健壮性、_________、时间复杂度、空间复杂度五个方面。 2.在数据结构中，数据的逻辑结构有线性结构、图结构、________________、_______________四种，物理实现上有顺序结构、索引结构、___________、_____________四种。 第三章线性表 一．选择题 1.在一个单链表HL中,若要向q所指结点之后插入一个指针p指向的结点,则执行. A. HL=p; p->next=HL B. P->next=HL; HL=p C. P->next=q->next; q->next=p D. P->next=q->next; q=p->next 2.在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移个元素。 A、n-i B、n-i+1 C、n-i-1 D、i 3.在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n+1)时，需要从前向后依次前移个元素。 A、n-i B、n-i+1 C、n-i-1 D、i 4.在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为。 A、n B、n/2 C、(n+1)/2 D、(n-1)/2 5.在一个单链表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; 6.在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行。 A、q->next = p->next ; p->next = q; B、p->next = q->next; q = p; 数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 实验容 1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。 3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。 5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6．输入整型元素序列利用有序表插入算法建立一个有序表。 7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8．编写一个主函数,调试上述算法。 #include #define OVERFLOW 0 #define MAXSIZE 100 typedef int ElemType; typedef struct list {ElemType elem[MAXSIZE]; int length; }Sqlist; void Creatlist(Sqlist &L) {int i; printf("请输入顺序表的长度："); //输入一组整型元素序列，建立一个顺序表。 scanf("%d",&L.length); for(i=0;i 江南大学现代远程教育第一阶段练习题及答案 考试科目:《数据结构》第一章至第四章（总分100分） ______________学习中心（教学点）批次：层次： 专业：学号：身份证号： 姓名：得分： 一、选择题（每题3分，共30分） 1、在树形结构中，数据元素间存在（）的关系。 Ａ、一对一Ｂ、一对多Ｃ、多对多Ｄ、除同属一个集合外别无关系 2、下列说法中错误的是（）。 Ａ、数据对象是数据的子集 Ｂ、数据元素间关系在计算机中的映象即为数据的存储结构 Ｃ、非顺序映象的特点是借助指示元素存储地址的指针来表示数据元素间逻辑关系 Ｄ、抽象数据类型指一个数学模型及定义在该模型上的一组操作 3、下列不属算法特性的是（）。 Ａ、有穷性Ｂ、确定性Ｃ、零或多个输入Ｄ、健壮性 4、在长为n的顺序表中删除一个数据元素，平均需移动（）个数据元素。 Ａ、n Ｂ、n-1 Ｃ、n/2 Ｄ、(n-1)/2 5、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。 Ａ、顺序表Ｂ、双链表Ｃ、带头结点的双向循环链表Ｄ、单循环链表 6、在一个可存放n个数据元素的顺序栈中，假设以高地址端为栈底，以top为栈顶指针，当向栈中压入一个数据元素时，top的变化是（）。 Ａ、不变Ｂ、top=n Ｃ、top++ Ｄ、top-- 7、设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则删除一个结点的操作是（）。 Ａ、rear=front->next Ｂ、rear=rear->next Ｃ、front=front->next Ｄ、front=rear->next 8、判定一个栈顶指针为S且不带头结点的链栈为空栈的条件是（）。 Ａ、S Ｂ、S->next Ｃ、S->next==NULL Ｄ、!S 9、设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则判定该队中只有一个结点的条件是（）。 Ａ、front->next Ｂ、rear->next Ｃ、front==rear Ｄ、front!=rear 10、串的长度是指（）。 《数据结构》课程设计题目 (程序实现采用C语言) 题目1：猴子选王（学时：3） 一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。 //链表 #include { pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead; // 构成环状链表 } void KickFromRing(RingNodePtr pHead, int n) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == n) { // 踢出环 printf("\n%d", pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr; 绪论和线性表习题 一、选择题 1.在一个单链表中，若p↑结点不是最后结点，在p↑之后插入s↑结点，则实行( )。 A. s->next=p；p->next=s; B、s->next=p->next; p->next=s； C. s->next=p->next;p=s; D. p->next=s;s->next=p; 2.与单链表相比,双链表优点之一( ). A.插入删除操作更简单. B.可随机访问 C.可省略表头指针和表尾指针 D、顺序访问相临结点更灵活 3.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为( ) A、 n-i+1 B.n-i C.i D.i-1 4.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( ) A.顺序表 B.用头指针表示的单循环链表 C、用尾指针表示的单循环链表 D.单链表 5.在需要经常查找结点的前驱与后继的场合中，使用( )比较合适。 A.单链表B、双链表 C.顺序表 D.循环链 表 6.下面关于线性表的叙述中，错误的为( ) A.顺序表使用一维数组实现的线性表 B.顺序表必须占用一片连续的存储单元 C.顺序表的空间利用率高于链表 D、在链表中，每个结点只有一个链域 7.带头结点head的单链表为空的判断条件是( ) A. head=NUIL B、head->next=NUIL C. head->next=head D. head!=NUIL 8.线性表通常采用两种存储结构是( ) A、顺序存储结构和链式存储结构 B.散列方式和索引方式 C.链表存储结构和数组 D.线性存储结构和非线性存储结构 9．线性表采用链式存储时，结点的存储地址（） A．必须是不连续的 B、连续与否均可 C．必须是连续的 D．和头结点的存储地址相连续 10．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（） A．O（1） B．O（n） C、 O（m） D．O（m+n） 数据结构经典例题 1.设计一个算法将L拆分成两个带头节点的单链表L1和L2。 void split(LinkList *&L,LinkList *&L1,LinkList *&L2) { LinkList *p=L->next,*q,*r1; //p指向第1个数据节点 L1=L; //L1利用原来L的头节点 r1=L1; //r1始终指向L1的尾节点 L2=(LinkList *)malloc(sizeof(LinkList));//创建L2的头节点 L2->next=NULL; //置L2的指针域为NULL while (p!=NULL) { r1->next=p; //采用尾插法将*p(data值为ai)插入L1中 r1=p; p=p->next; //p移向下一个节点(data值为bi) q=p->next; //由于头插法修改p的next域,故用q保存*p的后继节点 p->next=L2->next; //采用头插法将*p插入L2中 L2->next=p; p=q; //p重新指向ai+1的节点 } r1->next=NULL; //尾节点next置空 } 2.查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。 typedef struct LNode {int data; struct LNode *link; } *LinkList; int Searchk(LinkList list,int k) { LinkList p,q; int count=0; p=q=list->link; while (p!=NULL) { if (count 第四章串 习题4 一、选择题 1.串是一种分外的线性表，其分外性体现在（）。 A.可以顺序存储 B.数据元素是一个字符 C.可以连接存储 D.数据元素可以是多个字符 2.有两个串P和Q，求P在Q中首次出现的位置的运算称为（）。 A.模式匹配 B.联接 C.求子串 D.求串长 3.设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非通俗子串（非空且例外于S本身）的个数为（）。 A.n2 B.（n2/2）+（n/2） C.（n2/2）+（n/2）-1 D.（n2/2）-（n/2）-1 4.设串s1=“ABCDEFG”,s2=“PQRST”，函数concat（x，y）返回x和y串的连接串，subString（s，i，j）返回串s的从序号i的字符开始的j个字符组成的子串，Strlength（s）返回串s的长度，则concat（subString（s1，2，Strlength （s2）），subString(s1，Strlength（s2），2)））的结果串是（）。 A.BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF 5.顺序串中，根据空间分配方式的例外，可分为（）。 A.直接分配和间接分配 B.静态分配和动态分配 C.顺序分配和链式分配 D.随机分配和不变分配 6.设串S=“abcdefgh”，则S的所有非通俗子串（除空串和S自身的串）的个数是（）。 A.8 B.37 C.36 D.35 7.设主串的长度为n，模式串的长度为m，则串匹配的KMP算法时间复杂度是（）。 A.O(m) B.O（n） C.O（m+n） D.O（n*m） 8.已知串S=“aaab”，其next数组值为（）。 A.0123 B.1123 C.1231 D.1211 二丶填空题 1.在空串和空格串中，长度不为0的是（）。 2.空格串是指（），其长度等于（）。 3.按存储结构的例外，串可分为（）、（）和（）。 4.C语言中，以字符（）表示串值的终结。 5.在块链串中，为了提高存储密度，应该增大（）。 6.假设每个字符占1个字节，若结点大小为4个字节的链串的存储密度为50％，则其每个指针占（）个字节。 7.串操作虽然较多，但都可以通过五中基本操作（）、（）、（）、（）和（）构成的最小子集中的操作来实现。 8.设串S=“Ilikecomputer.”，T=“com”，则Length（S）=（），Index（S,T,1）=（）。 9.在KMP算法中，next[j]只与（）串有关，而与（）串无关。 10.字符串“ababaaab”的nextval函数值为（）。 11.两个字符串相等的充分必要条件是（）。 12.实现字符串复制的函数strcpy为： 基本概念典型例题 一、单项选择题 [例6-1]数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。其中，D是( ①)的有穷集合，R是D上( ②)的有限集合。 ①A.算法B. 数据元素C. 数据操作D. 逻辑结构 ②A. 操作B. 映像C. 存储D．关系 解析：由数据结构的集合形式化定义可知，本题答案为：①B；②D。 [例6-2]数据的常用存储结构中不包括( )。 A．顺序存储结构B．线性结构C．索引存储结构D．散列存储结构 解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储 方法和散列存储方法。由此可知，本题答案为：B。 [例6-3] 算法指的是( ①)，它必须具备( ②)这三个特性。 ①A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法 ②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性D．易读性、稳定性、安全性 解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。它 必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。由此可知，本 题答案为：①㈠②B。 [例6-4] 在下面的程序段中，对x的赋值语句的执行频度为( )。 for(i=0；i 第四章习题（P111-113） 一、复习题 1、试述数据和数据结构的概念及其区别。 数据是对客观事物的符号表示，是信息的载体；数据结构则是指互相之间存在着一种或多种关系的数据元素的集合。（P93） 2、列出算法的五个重要特征并对其进行说明。 算法具有以下五个重要的特征：有穷性：一个算法必须保证执行有限步之后结束。确切性：算法的每一步骤必须有确切的定义。输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件。输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法没有实际意义。可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。（P95） 3、算法的优劣用什么来衡量试述如何设计出优秀的算法。 时间复杂度空间复杂度（P97-98） 4、线性和非线性结构各包含哪些种类的数据结构线性结构和非线性结构各有什么特点 线性结构用于描述一对一的相互关系，即结构中元素之间只有最基本的联系，线性结构的特点是逻辑结构简单。所谓非线性结构是指，在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树型和图型结构就是其中十分重要的非线性结构，可以用来描述客观世界中广泛存在的层次结构和网状结构的关系。（P99-105） 5、简述树与二叉树的区别；简述树与图的区别。 树用来描述层次结构，是一对多或多对一的关系；二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。图也称做网，是一种比树形结构更复杂的非线性结构。在图中，任意两个节点之间都可能相关，即节点之间的邻接关系可以是任意的，图表示的多对多的关系。（P102-P104） 6、请举出遍历算法在实际中使用的例子。 提示：根据实际生活中需要逐个访问处理的情况举例。 7、编写一个算法，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。 提示：根据查找算法和串中求子串的算法，查找输入串中以单个字符形式的子串。 8、若对有n个元素的有序顺序表和无序顺序表进行顺序搜索，试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同 (1) 搜索失败； (2) 搜索成功，且表中只有一个关键码等于给定值k的对象； (3) 搜索成功，且表中有若干个关键码等于给定值k的对象，要求一次搜索找出所有对象。 1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学1998 三、1 （5分）】 LinkedList Union(LinkedList la,lb) { pa=la->next; pb=lb->next; la->next=null; while(pa!=null && pb!=null) ∥当两链表均不为空时作 if(pa->data<=pb->data) { r=pa->next; pa->next=la->next; ∥将pa结点链于结果表中，同时逆置。 la->next=pa; pa=r; } else {r=pb->next; pb->next=la->next; ∥将pb结点链于结果表中，同时逆置。 la->next=pb; pb=r; } while(pa!=null) ∥将la表的剩余部分链入结果表，并逆置。 {r=pa->next; pa->next=la->next; la->next=pa; pa=r; } while(pb!=null) {r=pb->next; pb->next=la->next; la->next=pb; pb=r; } } 1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。【南京理工大学1997 四、3（15分）】 LinkedList Union(LinkedList ha, hb)∥ha和hb是两个无头结点的数据域值递增有序的单链 ｛LinkedList 表，本算法将hb中并不出现在ha中的数据合并到ha中，合并中不能破坏hb链表。 la; la=(LinkedList)malloc(sizeof(LNode)); la->next=ha; pa=ha; pb=hb; pre=la; while(pa&&pb) if(pa->data 11． 写算法，实现顺序串的基本操作 StrReplace(&s,t,v) r1 中第 index 个字符起求出首次与串 r2 相同的子串的起始位置。 写一个函数将顺序串 s1 中的第 i 个字符到第 j 个字符之间的字符用 s2 串替换。 写算法，实现顺序串的基本操作 StrCompare(s,t) 。 第四章习题 1. 设 s=' I AM A STUDENT , t= ' GOO D, q=' WORKER 给出下列操作的结果: StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1); StrIndex(s, ' A ' ,4); StrReplace(s, ' STUDEN 'T,q); StrCat(StrCat(sub1,t), StrCat(sub2,q)); 2. 编写算法，实现串的基本操作 StrReplace(S,T,V) 。 3. 假设以块链结构表示串，块的大小为 1，且附设头结点。 试编写算法，实现串的下列基本操作： StrAsign(S,chars) ； StrCopy(S,T) ； StrCompare(S,T) ； StrLength(S) ； StrCat(S,T) ； SubString(Sub,S,pos,len) 。 4． 叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变 量的值。 5． 已知：S=”(xyz)* ” ,T= ”(x+z)*y ”。试利用联接、求子串和置换等操作，将 S 转换为T. 6． S 和T 是用结点大小为1的单链表存储的两个串，设计一个算法将串 S 中首次与T 匹配的子串逆 置。 7． S 是用结点大小为4的单链表存储的串，分别编写算法在第k 个字符后插入串T ,及从第k 个字符 删除 len 个字符。 以下算法用定长顺序串： 8． 编写下列算法： 1) 将顺序串 r 中所有值为 ch1 的字符换成 ch2 的字符。 2) 将顺序串 r 中所有字符按照相反的次序仍存放在 r 中。 3) 从顺序串 r 中删除其值等于 ch 的所有字符。 5) 从顺序串 r 中删除所有与串 r1 相同的子串。 从顺序串 9． 10． 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 第四章串 重点难点 理解"串"类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作；掌握串类型的各种存储表示方法；理解串的两种匹配算法。 典型例题 1、简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；【解】 （1）空串是指不包含任何字符的串，它的长度为零。 空白串是指包含一个或多个空格的串，空格也是字符。 （2）串常量是指在程序中只可引用但不可改变其值的串。 串变量是可以在运行中改变其值的。 （3）主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。 （4）静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。 动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。 2、以HString为存储表示，写一个求子串的算法。 【解】HString 是指以动态分配顺序串为存储表示，其定义为： typedef struct { char *ch; int length; }HString; void *substr( HString *sub,HString *s,int pos,int len) {//用sub返回串s的第pos个字符起长度为len的子串。sub初始时为一空串 //pos的合法位置为0<=pos<=s->length-1 int i; if (pos<0||pos>s->length-1||len<=0) Error("parameter error!");//参数不合法，子串为空串 if (s->length 典型题目分类 §1 概述 ［全真模拟试卷３选择题３］数据结构中，与计算机无关的是数据的 Ａ存储结构Ｂ物理结构Ｃ逻辑结构Ｄ物理和存储结构 答案：Ｃ ［全真模拟试卷５选择题１］数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及Ａ数据的存储结构Ｂ计算方法Ｃ数据映象Ｄ逻辑存储 答案：Ａ ［全真模拟试卷５选择题３］在计算机中，算法是指 Ａ加工方法Ｂ解决方案的准确而完整的描述 Ｃ排序方法Ｄ查询方法 答案：Ｂ ［全真模拟试卷１填空题１］算法的基本特征是可行性、确定性、和拥有足够的情报。 答案：有穷性 ［全真模拟试卷６选择题２］算法分析的目的是 Ａ找出数据结构的合理性Ｂ找出算法中输入和输出之间的关系Ｃ分析算法的易懂性和可靠性Ｄ分析算法的效率以求改进 答案：Ｄ ［全真模拟试卷６填空题１］在算法正确的前提下，评价一个算法的两个标准是。答案：时间复杂度和空间复杂度［专家预测试卷３填空题１］算法的工作量大小和实现算法所需的存储单元多少分别称为算法的。 答案：时间复杂度和空间复杂度 ［全真模拟试卷３选择题１］算法的空间复杂度是指 Ａ算法程序的长度Ｂ算法程序中的指令条数 Ｃ算法程序所占的存储空间Ｄ执行过程中所需要的存储空间答案：Ｄ §2 线性表 ［全真模拟试卷６选择题３］线性表Ｌ＝（a1,a2,……,a i,……,a n），下列说法正确的是 Ａ每个元素都有一个直接前件和直接后件 Ｂ线性表中至少要有一个元素 Ｃ表中诸元素的排列顺序必须是由小到大或由大到小 Ｄ除第一个元素和最后一个元素外，其余每个元素都有且只有一个直接前件和一个直接后件 答案：Ｄ ［全真模拟试卷７选择题１］下列叙述正确的是 Ａ线性表是线性结构Ｂ栈和队列是非线性结构 Ｃ线性链表是非线性结构Ｄ二叉树是线性结构 答案：Ａ ［专家预测试卷３选择题１］根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成 Ａ动态结构和静态结构Ｂ紧凑结构和非紧凑结构 Ｃ线性结构和非线性结构Ｄ内部结构和外部结构 答案：Ｃ ［全真模拟试卷３填空题１］数据的逻辑结构有线性结构和两大类。 答案：非线性结构 ［专家预测试卷１选择题３］线性表的顺序存储结构和线性表的链式存储结构分别是 Ａ顺序存取的存储结构，顺序存取的存储结构 Ｂ随机存取的存储结构，顺序存取的存储结构 Ｃ随机存取的存储结构，随机存取的存储结构 Ｄ任意存取的存储结构，任意存取的存储结构 答案：Ｂ ［全真模拟试卷５填空题１］长度为ｎ的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为。 答案：ｎ/2 §3 栈和队列 ［全真模拟试卷１选择题１］栈和队列的共同特点是 Ａ都是先进先出Ｂ都是后进先出 Ｃ只允许在端点处插入和删除元素Ｄ没有共同点 答案：Ｃ ［全真模拟试卷２选择题３］如果进栈序列为e1,e2,e3,e4，则可经典数据结构上机题_答案解析
数据结构第1阶段练习题
数据结构经典题目c语言代码
数据结构 习题
数据结构经典例题
数据结构课后习题第四章
数据结构典型例题
第4章数据结构与算法习题与答案
数据结构经典算法试题
数据结构课后习题及解析第四章
数据结构课后习题详解(超完整,超经典)
数据结构C语言版第四章 串
[IT认证]全国计算机等级考试《数据结构》典型试题