第一章绪论
一、内容提要
1 数据结构研究的内容。
2 基本概念:数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型、多形数据类型。
3 算法的定义及五个特征。
4 算法描述:类PASCAL语言。
5 算法设计要求。
6 算法分析。
二、学习重点
1 数据结构的“三要素”:逻辑结构、物理(存储)结构及在这种结构上所定义的操作(运算)。
2 抽象数据类型的定义、表示和实现方法。
3 类PASCAL书写规范,过程(函数)中值参和变参的差别,过程调用规则。
4 用计算语句频度来估算算法的时间复杂度。
三、例题解析
1 写出以下各语句执行次数(左边括号内数字为语句序号)
(1) FOR i:=1 TO n DO
(2) FOR j:=1 to n DO
(3) [ c[I,j] := 0;
(4) FOR k:=1 TO n DO
(5)(5)c[I,j]:=c[I,j]+a[I,k]*b[k,j]
]
[答案]:各语句执行次数(频度)分别为n+1,n(n+1), n2 , n2(n+1), n3
[分析]:最容易发生的错误,是将第一个语句的执行次数答成n。
2 编写最优算法,从小到大依次输出顺序读入的三个整数
PROC asscending;
{本算法对读入的三个整数进行排序,然后按从小到大输出}
{算法中核心语句如下}
read(a,b,c);
IF a>b
THEN [t:=a; a:=b; b:=t]; {a,b按正序排序} IF b>c
THEN [t:=c; c:=b; {c为最大}
IF a ELSE [b:=a; a:=t] {a,b正序} WRITELN(a:4,b:4,c:4); ENDP; {assending} [分析]:本题正确算法有多种,但上面是最优算法:最好情况下只经过两次比较且无数据移动,而在最 坏情况下,也只是经过三次比较,七个赋值语句就完成了排序。 在本课程教学中,强调“好”的算法, 不仅仅是结果正确, 而且是最优的算法。这与PASCAL语言教学中的要求有很大不同。 算法是供人来阅读的,必须牢记这一点。算法中语句的书写格式采用缩进规则,保留字用大写 ,其余标识符小写,提高了算法的易读性。 第二章第二章线性表 一、内容提要 1.线性表是元素间约束力最强的一类数据结构。 2.线性表的逻辑结构定义,对线性表定义的操作。 3.线性表的存储结构:顺序存储结构和链式存储结构。 4.线性表的操作在两种存储结构中的实现。 5.一元多项式的线性表表示方法,及高次(稀疏)多项式的抽象数据类型定义、表示和加法的实现。 二、学习重点 1.1.线性表的逻辑结构,指线性表的数据元素间存在着线性关系。在 顺序存储结构中,元素存储的先后位置反映出这种线性关系,而在链 式存储结构中,是靠指针来反映这种关系的。 2.2.顺序存储结构用向量(一维数组)表示,给定下标,可以存取相 应元素,属于随机存取的存储结构。 3.3.尽管“只要知道某结点的指针就可以存取该元素”,但因链表的 存取都需要从头指针开始,顺链而行,故链表不属于随机存取结构。 4.4.链表是本章学习的重点和难点。要理解头结点,首元结点和元素 结点的差别。理解头结点是为了在插入、删除等操作时,为了算法的 统一而设立的(若无头结点,则在第一元素前插入元素或删除第一元 素时,链表的头指针总在变化)。掌握通过画出结点图来进行链表的 生成、插入、删除、遍历等操作。 5.5.链表操作中应注意不要使链意外“断开”。因此,若在某结点前 插入一个元素,或删除某元素,必须知道该元素的前驱结点的指针。 6.6.从时间和空间复杂度的角度综合比较线性表在顺序和链式两种存 储结构下的特点。 7.7.静态链表是又一重点和难点。应和链表进行比较、理解。例如,在有头结点的链表情况下,第一元素是p:=la^.next,而在静态链表中 则i:=sa[0].next;相对p:=p^.next,有i:=sa[i].next来找到第i个元素的 后继。 三、例题解析 1.设线性表以顺序存储结构存于a(1..n)中,试编写算法将该线性表就地逆置。 【分析】向量逆置有几种方法,如逆向读入到另一数组中,在正向对应赋值,即: FOR i:=n DOWNTO 1 DO b[n-i+1]:=a[i]; FOR i:=1TO n DO a[i]:=b[i]; 这里要求“就地逆置”,即不能另用一数组空间。 【算法】 PROC invert(V AR a:arr; n:integer); {a是存储线性表的一维数组,有n 个元素,本算法将a逆置。} FOR i:=1TO (n DIV 2) DO a[i]?a[n-i+1]; endp; 【讨论】将n个元素的一维数组逆置,为什么循环控制变量用n div 2,而不用n? 2.编写在单链表上进行排序的算法 【分析】这里使用插入排序。链表中插入元素要知道待插入元素 位置的前驱,以pre表示之。结束的条件是链表为 空。 【算法】 PROC insertsort(V AR la:linklist); {la是带头结点的单链表的指针,本算法将链表中元素 正序排序。算法的基本思想是先假定第一个元素有序, 然后从第二个元素开始,依次插入到有序的表中,直 到全部元素插入完为止} p:= la^.next^.next;{假定链表非空,即至少有一个结 点} la^.next^.next:=nil;{设有序链表中当前只有一个结 点} found:=false; WHILE (p<>nil)AND NOT found DO [s:=p^.next;{记住下一个结点} pre:=la; q:=la^.next; found:=false; WHILE(q<>nil)AND NOT found DO IF q^.data q:=q^.next] ELSE found:=true; p^.next:=q; pre^.next:=p;{p结点插入} p:=s;{取下一个结点} ] ENDP; {insertsort} 【讨论】算法中found为一布尔变量,为的是在链表到尾前,如找到p的插 入位置,即可退出WHILE循环。这里循环条件未写成: (p<>nil)AND (q^.data 因为若q=nil ,则再引用q^.data是无意义的。请记住这种退出循环,引入布尔变量的作法。 3.设两个非递减有序的线性表各有m和n个元素(m>0,n>0),分别存于一维数组a和b中,且a 的存储空间足够大。试编写算法将两线性表合并成一线性表,结果 仍是非递减有序,要求算法的时间复杂度是o(m+n)。 【分析】两个有序线性表合并成一个有序表,教材中已有讨论,算法非常简单。 本算法要求复杂度为O(m+n),这是着重点。题目叙述中有“a的空间足 够大”,暗示出若将m+n个元素合并到a中,不会溢出。为使数据移动次 数最少,应先将两表中最大元素置于m+n的位置上,然后相应指针减1, 再比较之,直到两表中有一个指针减到0,则结束,否则,将b中剩余元 素传到a中相应位置即可。 【算法】 PROC union(V AR a:seqlisttp;b:seqlisttp); {a,b是两个非递减有序表,顺序存储结构存储,各有m和n个元素, 本算法将两表合并到a中,仍为有序表,算法时间复杂度为O(m+n)} i:=m; j:=n ;k:=m+n; {i,j,k分别为表a,b和结果表的指针} WHILE (i>0) AND (j>0) DO IF a[i]>b[j] THEN [a[k]:=a[i]; i:=i-1; k:=k-1] ELSE [a[k]:=b[j]; j:=j-1; k:=k-1]; WHILE (j>0) DO [a[k]:=b[j]; j:=j-1; k:=k-1]; {若b表中尚有元素,则传至a中相应位置} 【讨论】本算法至多比较m+n次,往a中赋值m+n次。最好情况是比较n次,往a 中赋值n次,该种情况是b中最小元素不小于a中最大元素。 问题:为什么在退出第一个WHILE循环后,不讨论(即没有)WHILE i>0的 情况? 第三章栈和队列 一、一、内容提要 1.1.从数据结构角度讲,栈和队列也是线性表,其操作是线性表操作的子集,属操作受限的线性表。但从数据类型的角度看,它们是和线性表大不相同的重要抽象数据类型。 2.2.栈的定义及操作。栈是只准在一端进行插入和删除操作的线性表,该端称为栈的顶端。 3.3.栈的顺序和链式存储结构,及在这两种结构下实现栈的操作。 4.4.栈的应用:表达式求值,递归过程及消除递归。 5.5.队列的定义及操作,队列的删除在一端(尾),而插入则在队列的另一端(头)。 因此在两种存储结构中,都需要队头和队尾两个指针。 6.6.链队列空的条件是首尾指针相等,而循环队列满的条件的判定,则有队尾加1等于 队头和设标记两种方法。 二、二、学习重点 1.栈和队列操作在两种存储结构下的实现。 2.中缀表达式转成前缀、后缀表达式并求值。 3.用递归解决的问题:定义是递归的,数据结构是递归的,及问题的解法是递归的,掌握典型问题的算法。 4.4.链队列删除时为空的处理(令队尾指针指向队头)。特别是仅设尾指针的循环链队 列的各种操作的实现。 5.5.循环队列队空定义为队头指针等于队尾指针,队满则可用一个单元(教材中所示) 及设标记办法(下面例题)。这里特别注意取模运算。 6.6.在后续章节中要注意栈和队列的应用,如串中心对称的判定,二叉树遍历的递归 和非递归算法,图的深度优先遍历等都用到栈,而树的层次遍历、图的宽度优先遍历等则用到队列。 三、三、例题解析 1.1.两栈共享一向量空间,编写入栈和出栈算法。 TYPE TwoWayStack=RECORD {双栈共享一向量空间} elem:ARRAY[1..m] OF elemtype; top:ARRAY[0..1] OF 0..m+1; {两个栈顶指针} END; PROC inistack(VAR tws:TwoWayStack); {初始化} {初始化双向栈tws为空} tws.top[0]:=0; { 左端栈指针} tws.top[1]:=m+1; { 右端栈指针} ENDP; {inistack} PROC PUSH(VAR tws:TwoWayStack;i:0..1; x:elemtype;VAR ofw:boolean); {若双向栈tws不满,则将x插入到i端,成功时ofw为true,失败为false} IF(tws.top[1]-tws.top[0])<>1 THEN {栈未满} CASE i OF 0:tws.top[0]:=tws.top[0]+1;tws.elem[tws.top[0]]:=x;ofw:=true 1:tws.top[1]:=tws.top[1]-1;tws.elem[tws.top[1]]:=x;ofw:=true ENDC ELSE ofw:=false;( 栈满) ENDP; {push} PROC POP(VAR tws:TwoWayStack;i:0..1;VAR x:elemtype;VAR underflow:boolean); {若双向栈tws非空,则将i端退栈,栈空时underflow为true} CASE i OF 0:IF tws.top[0]=0 {栈空} THEN[underflow:=true;return(underflow)] ELSE[ tws.top[0]:=tws.top[0]-1; x:=tws.elem[tws.top[0]+1]; {弹出元素} ]; 1:IF tws.top[1]=m+1 {栈空} THEN[underflow:=true;return(underflow)] ELSE[ tws.top[1]:=tws.top[1]+1; x:=tws.elem[tws.top[1]-1]; {弹出元素} ]; ENDC ENDP; {pop } 【讨论】上面算法中用0和1代表两端,且按操作在哪端来分两种情况进行讨论,逻辑清楚。也可用一个公式表示插入(进栈)和删除(退栈)指针位置。例如,插入时top=top+1-2*i,删除时top=top-1+2*i。表达简洁,但不如上面清楚易读。 2.2.将中缀表达式转换成后缀表达式,并进行表达式求值。 PROC trnssufix(VAR exp2:string;s:stack; exp1:string); {本算法将中缀表达式exp1转为后缀表达式exp2,使用运算符栈s} {算法基本思想是依次从中缀表达式读入字符w:若w是变量,直接送入结果表达式,若w 是运算符,则与栈顶运算符比较,若级别高,则进栈;若低,则栈顶元素退栈,并送入结果表达式,再取栈顶运算符比较,重复以上步骤;若w=’)’,则栈元素依次退栈,并送入结果表达式,直至')'退栈} initstring(exp2); initstack(s);push(s,’#’); op:=['+','-','*','/','(',')','#']; {操作符集合} read(w); WHILE NOT ((w='#') AND (GETTOP(OPTR)='#')) DO IF NOT (w IN op) THEN [ insert(exp2,w); read(w) ]; ELSE CASE precede(GETTOP(s),w) OF '<': [ PUSH(S,w); read(w) ]; '=': IF w=’)’ THEN {遇右括号后,运算符退栈并送结果表达式, 直至左括号} [ x:=POP(S); WHILE x<>’(‘ DO [insert(exp2,x);x:=POP(S)] read(w) ]; '>': [ b:=POP(S); insert(exp2,b)]; END; ENDP; PROC sufixeval(VAR exp2:string;s:stack; VAR sn:stack); {本算法对后缀表达式exp2求值,使用运算符栈s和操作数栈sn} {算法基本思想是逐字符从左到右顺序读入后缀表达式。若读入的字符w是数,则直接压入栈 sn中;若w是运算符,则与栈顶运算符比较,若级别高,则进栈;否则,从运算数栈弹出两个操作数,和从运算符栈弹出的一个运算符进行相应运算,结果存入操作数栈中。w运算符再与栈顶运算符比较优先级。直至后缀表达式处理完毕。这时sn栈中只剩一个数,即表达式结果。} initstring(sn); initstack(s); op:=['+','-','*','/','(',')','#']; {操作符集合} read(w); {从左到右顺序读入后缀表达式 } WHILE NOT empty(exp2) DO IF NOT (w IN op) THEN [ PUSH(sn,w); read(w) ]; ELSE CASE precede(GETTOP(s),w) OF '<': [ PUSH(s,w); read(w) ]; '>': [ a:=POP(sn);b:=POP(sn); theta:=POP(s); PUSH(sn,operate(a theta b)) ]; END; ENDP; { sufixeval} 3、用设标记来判定循环队列满,编写入队和出队的算法。 {本算法用设标记tag的办法,解决循环队列队满和队列空的判断问题,tag=0表示队列空,tag=1表示队列不空} TYPE cyclicqueue=RECORD {设头尾指针和标志域的循环队列} elem:=ARRAY[0..m-1] OF elemtype; rear,front:0..m-1 tag:0..1; {0为空,1为非空} END; PROC INITQUEDE(VAR cq:cyclicqueue); {初始化} cq.tag:=0;cq.tear:=cq.front:=0; ENDP; PROC ENQUEUE(VAR cq:cyclicqueue; x: elemtype); {cq是由头尾指针和标志域的循环队列,本算法是入队操作,若队列不满,} {则将x插入到队尾} IF (cq.tag=1) AND (cq.front=cq.rear) THEN return(false) {队满} ELSE[cq.rear:=(cq.rear+1) MOD m; cq.elem(cq.rear):=r; IF cq.tag=0 THEN cq.tag:=1 {由空变不空标记} ] ENDP; PROC DELQUEUE(VAR cq:cyclicqueue); {cq是由头尾指针和标志域的循环队列,本算法是出队操作,若队列非空} {则将队头元素出队} IF cq.tag=0 THEN return(false) {队空} ELSE[cq.front:=(cq.front+1) MOD m; IF cq.front=cq.rear THEN cq.tag:=0 {队空} ] ENDP; CONST m=maxlen; {队列长度} TYPE cyclicqueue=RECORD {只设尾指针和队列长度的循环队列} elem: ARRAY[0..m-1] OF elemtype; rear: 0..m-1; length: 0..m; {队列长度} END; PROC INIT_queue(VAR q:cyclicqueue); {初始化} q.rear:=0; q.length:=0; ENDP; FUNC add_queue(VAR q:cyclicqueue;x:elemtype):boolean; {q是由尾指针和长度标志的循环队列,本算法是入队操作,若队列不满,} {将x插入到队尾} IF q.length=m THEN add_queue:=false {队列满} ELSE [ q.rear:=(q.rear+1) mod m; q.elem[q.rear]:=x; q.length;=q.length+1; add_queue:=true {入队成功} ] ENDF; FUNC dd_queue(VAR q:cyclicqueue; x;elemtype):boolean; {q是由尾指针和长度标志的循环队列,本算法是出队操作,若队列不空,} {将将队头元素出列,并赋给x,队长度减1} IF q.length=0 THEN dd_queue:=false {队空} ELSE [front;=(q.rear-q.length+1+m) mod m x:=q.elem[front] q.length:=q.length-1 ] ENDF; 第四章第四章串 一、内容提要 1、1、是数据元素为字符的线性表,串的定义及操作。 2、2、的基本操作,编制算法求串的其它操作。 3、3、的存储结构,因串是数据元素为字符的线性表,所以存在“结点大小“的问题。静 态和动态(块链结构,堆结构)存储的优缺点。 4、4、朴素模式匹配算法及改进(KMP)算法。 二、学习重点 1、1、串的基本操作,编写串的其他操作(如index,replace等)。 2、在串的模式匹配中,求匹配串的nextval 函数值。 3、尽管朴素的模式匹配的时间复杂度是O(m*n), KMP算法是O(m+n),但在一般情况下,前者实际执行时间近似O(m+n),因此至今仍被采用。KMP算法仅在主串与模式串存在许多“部分匹配”时才显得比前者块的多,其主要优点是主串不回嗍。 5、5、串操作在存储结构下的实现。 三、例题解析 1、利用串的如下基本运算create(s),assign(s,t),length(s),substr(s,start,len),concat(s1,s2),编 写操作replace的算法 PROC replace(V AR s:string; t,v:string); {本算法实现串的置换操作,用串v置换串s中所有非重叠的t串。} i:=INDEX(s,t); {判s中有无t} IF i<>0 THEN [ CREATE (temp, ‘’); {t为临时串变量,存放部分结果} m:=LENGTH(t); n:=LENGTH(s); WHILE i<>0 DO [ ASSIGN (temp,CONCA T(temp,SUBSTR(s,1,i-1),v)); {用v替换t形成部分结果} ASSIGN (s,SUBSTR(s, i+m, n-i-m+1)); {t串以后形成新s串} n:= n-(i-1)-m; i:=INDEX(s,t); ] ASSIGN (s,CONCA T(temp,s)); {将剩余s连接临时串t再赋给s} ] ENDP; FUNC index(s1:string; t:string):integer; {本算法求串t在串s中的第一次出现。结果是:若t在s中,则给出串t的第一个字符在串s中的位置,若不存在,则返回0} j:=1;m:=length(s); n:=length(t); eq:=true; WHILE (j<=m-n+1) AND eq DO IF equal(substr(s,j,n),t) THEN eq:=false ELSE j:=j+1; IF j<=m+n-1 THEN index:=j ELSE index:=0 ENDF;{index} 【讨论】本题是用给定的基本操作,编写其它操作的算法。这种类型题较多,必须严格按题的要求来做,不准选择具体存储结构。否则,即使全对,也很难得分。 22设目标为t=’abcaabbabcabaacbacba’,模式串p=’abcabaa’; (1)计算P的NEXTV AL函数值; (2)不写出算法,只画出利用KMP算法进行模式匹配时每一趟的匹配过程; 【解答】 (1)P的NEXTV AL 函数值如下; j 1 2 3 4 5 6 7 _______________________________ 模式p a b c a b a a nextval(j) 0 1 1 0 1 0 2 (2) a b c a a b b a b c a b a a c b a c b a a b c a b 第一趟匹配 a b c 第二趟匹配 a 第三趟匹配 a b c a b a a 第四趟匹配成功 【讨论】为写NEXTV AL方便,可先写出NEXT函数值,在由此求NEXTV AL. 3、字符串s 满足下式,其中HEAD 和TAIL的定义同广义表类似,如HEAD(‘XYZ’)=’X’,TAIL(‘XYZ’)=’YZ’,则 S=concat(head(tail(s)),head(tail(tail(s))))=’dc’ 求字符串s。 可供选择的答案是(A)abcd (B) acbd (C) acdb (D) adcb 正确答案是(D)。 第五章数组和广义表 一、一、内容提要 1,1,数组的逻辑结构定义及存储, 2,2,稀疏矩阵(含特殊矩阵)的存储及运算。 3,3,广义表的定以及存储。 4,4,广义表运算的递归算法。 二、学习重点 1,1,数组(主要是二维)在以行序为主的存储中的地址计算方法。 2,2,特殊矩阵在压缩存储时的下标变换。 3,3,稀疏矩阵的三元组表存储结构及矩阵移植的算法。 4,4,稀疏矩阵的十字链表存储方法及十字链表生成算法。 5,5,广义表的HEAD和TAIL 运算。 6,6,给定广义表画出其存储结构。 7,7,从广义表的递归算法,掌握如何编写递归算法。 三、例题解析 1、字符串二维数组A[0..8,1..10] ,每个元素由6个字符组成,每个字符占一个存储单元,则(1)存放A需要多少个字节? (2)A的第8列和第5行共占多少字节? (3) 按行序存储时,A[8,5]和按列存储时哪个元素时的地址相同? 【解答】(1)540 (2)108 (3)A[3,10] 2、编写算法,将自然数1---n2按蛇形填入n x n矩阵中。 例如,(1—42)如右图所示。 【分析】本题要求在N的方阵中填人N2个数,关键是控 制 下标。设坐标原点在矩阵的左上角,且i是向下增长,j向 右增长。原点的坐标为(1,1)。 【算法】 PROC sqrmgc(VAR a:arr;n:integer); { 本算法将自然数1--n2按蛇形填入N X N 矩阵中,a 是二维数组} i:=1; j:=1; k:=1; WHILE (i<=n) AND (j<=n) DO [ WHILE (i<=n) AND (j>0) DO [ a[i,j]:=k; i:=i+1; j:=j-1; k:=k+1 ] IF j<1 THEN IF i<=n THEN j:=1 ELSE [j:=j+2;i:=n ] ELSE [i:=n; j:=j+2] WHILE (i>0) AND (j<=N) DO [ a[i,j]:=k; i:=i-1; j:=j+1; k:=k+1 ] IF i<1 THEN IF j<=n THEN i:=1 ELSE [i:=i+2;j:=n ] ELSE [j:=n; i:=i+2 ] ] ENDP; {sqrmgc} 3、求下列广义表操作结果: (1)(1)HEAD(TAIL(HEAD(((a,b),(c,d)))) (2)(2)TAIL(HEAD(TAIL(((a,b),(c,d)))) 【解答】(1)b (2) (d) 4 、利用广义表的HEAD和TAIL操作,写出如上题的表达式,把原子banana从下列 广义表中分离出来。 (1)(1)L1=(apple,(pear),((banana)),(((orange)))); (2)(2)L2=(apple,(pear,(banana),orange)); 【解答】(1) HEAD(HEAD(HEAD(TAIL(TAIL(L1))))) (2) HEAD(HEAD(TAIL(HEAD(TAIL(L1))))) 第六章第六章树和二叉树 一、内容提要 1、树是复杂的非线性数据结构,树,二叉树的递归定义,基本概念,术语。 2、二叉树的性质,存储结构。 3、二叉树的遍历算法(递归,非递归)。 4、线索二叉树 5、树的存储结构,树、森林的遍历及和二叉树的相互转换。 6、二叉树的应用:表达式求值、判定问题及哈夫曼树和哈夫曼编码。 二、学习重点 (本章内容是本课程的重点) 1、二叉树性质及证明方法,并能把这种方法推广到K叉树。 2、二叉树遍历的递归算法,本书中介绍了三种(先、中、后序)方法,另三种也应会用。前序和中序的非递归遍历。遍历是基础,由此导出许多实用的算法,如求二叉树的高度、各结点的层次数、度为0、1、2的结点数,二叉树的相似、全等、复制等等的算法。 3、由二叉树的遍历的前序和中序序列或后序和中序序列可以唯一构造一棵二叉树,手工模拟及编写算法。由前序和后序序列不能唯一确定一棵二叉树。 4、二叉树线索化的实质是建立结点在相应序列中的前驱和后继之间的直接联系。在何序(前、中、后)下进行何种(全、前驱、后继)线索化,并求某结点相应的前驱和后继。 5、完全二叉树的性质,顺序存储结构和二叉树链表存储结构的相互转换。 6、树的双亲表示法和孩子兄弟表示法间的相互转换。 7、树、森林和二叉树间的相互转换(“连线”、“切线”和“旋转”)。 8、哈夫曼树的定义、构造及求哈夫曼编码。 三、例题及分析 在二叉树中查找其数据域为x的结点。如存在,返回该结点指针,否则返回空指针。 【分析】可采用递归遍历算法。 【算法】 PROC search(bt:bitreptr; x:datatype); {bt 是bitreptr型的二叉树,x是待查找数据值,本算法递归遍历二叉树,在遍历中进行查找。算法中p是调用本过程的过程中定义的变量,初值为NIL,查找成功后,p指向数据域为x的结点。found是初值为false的变量。从本过程返回后,测试found以确定是否查找成功。} IF (bt<>NIL ) AND NOT found THEN [IF bt^.data=x THEN [ p:=bt; found:=true ] search (bt^.lchild, x); search (bt^.rchild, x); ] ENDP; {serch} 【讨论】 本算法核心语句有三个(即第一个THEN后的语句:第一个语句是“访问”根结点. 后两个语句是递归遍历(相对位置不变)。在这三个语句中,由“访问”语句所处位置不同(前、中、后),形成三种递归遍历方法:前序、中序和后序。 Found是为查到x就立即(不再遍历未遍历结点)而设立的。若要再考虑本算法的优化,则在两个调用语句中可加上 If (bt^.lchild<>NIL) AND NOT found 和 If (bt^.rchild<>NIL) AND NOT found 其优点是在左(右)为空时不必再调用,且一旦找到x就立即退出。 2.设二叉树采用二叉链表作为存储结构,试编写算法求二叉树的结点数。 【分析】 计算二叉树结点数的数学模型如下: f(bt)=0 若bt=nil f(bt)=f(bt^.lchild) +f(bt^.rchild) +1 否则 【算法】 FUNC nodes(bt:bitreptr):integer; IF bt=nil THEN nodes:=0 ELSE [ n1:=nodes(bt^.lchild) n2:=nodes(bt^.rchild) nodes:=ni+n2+1 ] ENDF {nodes} 【讨论】二叉树由根、左子树、右子树三部分组成,很多问题(如求叶子、度1、度2结点数),可分解到三部分求解,上面写出数学递归模型是有普遍意义的。例如: (1). 二叉树相似: f(t1,t2)=true若t1=t2=NIL f(t1,t2)=false若t1,t2中只有一个为NIL f(t1,t2)=f(t1^.lchild, t2^.lchild) AND f(t1^.rchild,t2^.rchild) 若t1,t2均不为NIL (2)求二叉树的叶子结点数 f(bt)=0 当bt=nil f(bt)=1 当bt左右子树均为空 f(bt)=f(bt^.lchild)+f(bt^.rchild) 否则 (3)求二叉树所有叶子结点的最大枝长: 0 若bt^.lchild=nil 且bt^.rchild=nil maxl(bt^.lchild)+1 若bt^.rchild=nil max= maxl(bt^.rchild+1) 若bt^.lchild=nil max(maxl(bt^.rchild+1) ,maxl(bt^.rchild))+1 否则 3.打印二叉树中结点x(假定存在)的所有祖先结点。 【分析】在二叉树的递归遍历等算法中,只有后序遍历才是最后访问根结点,因此有可能保留从根结点到待查结点的踪迹,这时可用栈,存放从根结点到x结点路径中的各祖先结点。 【算法】 PROC printansctr(bt:bitreptr; x:datatype); {bt 是bitreptr型的二叉树,x是待查找数据值,本算法输出X结点的各祖先结点。S是工作栈,存放X的祖先结点。查到X后,依次输出S中数据即可。} initstack(s); p:=bt; push(s,p); WHILE NOT empty(s) DO [ WHILE NOT empty(s) AND (p^.data<>x) DO [ push(s,p); p:=p^.lchild ] IF p^.data=x THEN WHILE NOT (empty(s)) DO [p:=pop(s); write(p^.data) ] ELSE {需要到右分枝去查x结点} [q:=nil; rend:=true; {rend是为了在右分枝不空时就退出循环} WHILE NOT empty(s) AND rend DO [p:=pop(s); IF p^.r=q THEN q:=p {右分枝为空时退栈} ELSE [ push(s,p);p:=p^.rchild; rend:=false] ] ENDP;{ printansctr} 第七章第七章图 一、内容提要 1.1.图的定义,概念、术语及基本操作。 2.2.图的存储结构。 3.3.图的遍历。 4.4.图的应用(连通分量,最小生成树,拓扑排序,关键路经,最短路经)。 二、学习重点 图是应用最广泛的一种数据结构,本章是这门课程的重点。 11基本概念中,连通分量,生成树,邻接点是重点。 22图是复杂的数据结构,也有顺序和链式两种存储结构:数组表示法(重点是邻接距阵)和邻 接表。这两种存储结构对有向图和无向图均适用。十字链表是有向图的另一种表示,将有向图的邻接表和逆邻接表合一。邻接多重表是无向图邻接表的改进,将边结点的数量减少一半(正好等于边的数量)。 33图的遍历是图的各种算法的基础,应熟练掌握图的深度、广度优先遍历,手工模拟图的遍历中栈和队列指针状态的变化。 44在(强)连通图中,主过程一次调用深(宽)度优先遍历过程(dfs/bfs),即可遍历完全部顶点,故可以用此方法求出连通分量的个数,并能画出遍历中形成的深(宽)度优先生成树。 55连通图的最小生成树不是唯一的,但最小生成树边上的权值之和是唯一的。应熟练掌握prim和kruscal算法,特别是手工分步模拟生成树的生成过程。 66拓扑排序是在有向图上对入度(先后)为零的顶点的一种排序,结果不唯一。关键路经是在拓扑有序的前提下求出来的,从源点到汇点的最长路径。应能掌握这两种算法,并熟练手工模拟。理解“减少关键活动时间能缩短工期”,是指该活动为所有关键路径所共有,且减少到尚未改变关键路经的前提下才有效。 77从单源点到其他顶点,以及各个顶点间的最短路经问题,掌握算法,并熟练手工模拟。 三、例题解析 1、用邻接多重表实现图的各种运算。 【分析】在邻接多重表中,每条边用一个结点表示,不象在邻接表中那样用两条边来表示。这在图的操作中,要比其他的存储结构要复杂的多。 PROC crt_graph ( var g:adjmulist); {g 为教材中已定义的adjmulist类型变量,本算法建立有n个结点e 条边的图的存储结构} FOR I := 1 TO n DO 【read (g[i].data; g[i].firstedge:=nil)】 {建立顶点向量,各顶点所指向的第一条边指针为nil} FOR r:= 1 TO e DO 【read (vi,vj); {读两结点} i:=loc_vertex(g,vi); j:=loc_vertex(g,vj) new(p); p^.ivex:=i; p^.jvex:=j; p^.ilink:=g[i].firstedge; g[i].firstedeg:=p {将边(vi,vj)分别插入顶点vi,vj的边结点链表中。} 】 ENDP;{crt_graph} 【讨论】在本算法中,设输入的边不含有重复边,即输入(vi,vj)后,即不应再输入 (vi,vj),也不应再输入(vj,vi)。否则,本算法应添加查询功能(即下面search 过程)。查询成功时该边不再加入到图的存储结构中。 FUNC search(g:adjmulist;I,j:1..vtxnum):edgeptr; {本算法在图g中查询顶点vi,vj间的边结点是否已建立。如是,则返回该边结点的指针,否则返回nil} p:=g[i].firstedge; found:=false WHILE (p<>NIL) AND NOT found DO IF p^.ivex=i {结点中ivel,jvex 域均可能为i} THEN IF p^.jvex=j THEN found := true ELSE p:=p^.ilink {顺ilink下找} ELSE IF p^.ivex=j {p^.jvex=i} THEN found :=true ELSE p:=p^.jlink {顺jlink下找}; ENDF; {search} PROC insert_edge (V AR g:adjmulist; vi,vj:vtxptr); {本算法在邻接多重表中插入边(vi,vj)} i:=loc_vertex(g,vi); j:=loc_vertex(g,vj); fp:=search(g , i , j ); IF fp:=nil {若边(vi,vj )在图中不存在} THEN 【new(p) ; p^.ivex:=i; p^.jvex:=j; p^.ilink:=g[i].firstedge; g[i].firstedge:=p; p^.jlink:=g[j].firstedge; g[j].firstedge:=p; 】 ENDP; {insert} PROC insert_vertex ( VAR g:adjmulist; v:vtxptr); {本算法在邻接多重表中插入顶点V。设顶点向量足够大,插入一顶点也就是加一个向量元素,设m是已有顶点数,则} g[m+1].data:=v ; g[m+1].firstedge:=nil; ENDP; {insert_vertex} PROC delete_edge ( V AR g:adjmulist; vi,vj:vtxptr); {本算法在邻接多重表g中删除边(vi,vj)} i:=loc_vertex(g,vi); j:=loc_vertex(g,vj); fp:=search(g , i , j ); IF fp<> nil THEN 【p:=g[i].firstedge; q:=nil;{修改i的链表边结点(vi,vj)的前驱的指针} WHILE p<> fp DO 【q:=p; IF p^.ivex=i THEN p:=p^.ilink ELSE p:=p^.jlink 】 IFq=nil {删除的边是顶点vi的第一边结点} THEN IF p^.ivex=i THEN g[i].firstedge:=p^.ilink ELSE g[i].firstedge:=p^.jlink ELSE {所删除的不是vi的第一边结点} IF q^.ivex=i THEN IF p^.ivex=i THEN q^.ilink:=p^.ilink ELSE q^.ilink:=p^.jlink ELSE IF p^.ivex=i THEN q^.jlink:=p^.ilink ELSE q^.jlink:=p^.jlink; p:=g[j].firstedge; q:=nil; {修改j的链表边结点(vi,vj)的前驱的指针} {从vj的边结点链表中找到(vi,vj)边,修改前驱指针,算法同上,故略} dispose(fp); 】 ENDP;{delete_edge} PROC delete_vertex ( V AR g:adjmulist; v:vtxptr); {删除顶点的算法,该顶点删除后,在其顶点向量数据域中作标记,且要删除与该顶点相关的所有边} i:=loc_verdex (g,v); p:=g[i].firstedge; WHILE p<> nil DO 【IF p^.ivex=I THEN s:=p^.ilink {记住下一边结点} ELSE s:=p^.jlink; IF i=p^.ivex THEN delete_edge (g:,v,g[p^.jvex].data) ELSE delete_edge (g:,v,g[p^.ivex].data) p:=s 】 ENDP; {delete_vertex} 2、编写对图的深度优先非递归遍历算法。 【分析】使用栈,调用过程的算法同教材,对被调用过程编写如下: PROC dfs(g:adjlist; v0:vtxptr); {本算法从顶点v0 开始。在图g 中进行深度优先遍历。算法中visited是在主过程中已赋值false的辅助数组,s是元素为边(弧)结点的工作栈。} initstack(s); write(v0); visited[v0]:=true; p:=g[v].firstarc; WHILE (p<>nil) AND NOT empty(s) DO 【WHILE p<>nil DO IF visited[p^.adjvex] THEN p:=p^.nextarc ELSE 【write ( p^.adjvex); push(s,p); visited [p^.adjvex]:=true; p:=g[p^.adjvex].fistarc; 】 IF NOT empty (s) THEN 【p:=pop(s); p:=p^.nextarc 】 】 ENDP; {dfs} 第八章动态存储管理 一、内容提要 1.1.动态存储管理指的是在用户需要时给分配内存,而在用户结束使用时,系统要收回用户所占空间。 2.2.可利用空间表的三种结构形式:结点固定大小;分几种规格;任意大小。 3.3.可利用空间表的两种组织形式:目录表,链表。 4.4.可利用空间表的分配方式:首次拟合法,最佳拟合法,最差拟合法。 5.5.可利用空间表的分配和回收的两种基本实现方法:边界标识法,伙伴系统。 6.6.无用单元回收和紧缩存储的概念。 二、学习重点 1、概念:可利用空间表及分配方式,紧缩存储,伙伴系统,等。 2、边界表示法的分配及回收算法。 3、伙伴系统的分配及回收算法。 三、例题解析 设有大小为512字节的存储,有6个用户申请大小分别为23,45,52,100,11和19 字节的存储空间,然后再顺序释放大小为45,52 和11的占用空间。假设以伙伴系统实现动态存储管理。 1.1.画出可利用空间表的初始化状态。 2.2.画出为6个用户分配的存储空间后可利用空间表的状态,以及每个用户得到的存储块的起始地址。 3.3.画出在3个占用块回收后可利用空间表的状态。 【解答】 9,所以初始化为: 2, (1) 23<=25=32, 所以要分配25字节一块占用块首址0。因无25空闲块,故原先29块分裂为28、、27、26、25各一块,首址依次为256,128,64,32。(0—31给了申请23的用户)。(2)45〈=26=64,故将26空闲块(64—127)给了该用户,其首址为64。 (3)因52〈=26=64,这时已无26大小空闲块,故将27块分裂,一块26大小给了用户(128—129),起始地址128,其伙伴起始地址192(192—255)挂到26空闲块链表中。(4)100〈=27=128,因无27空闲块,28块产生分裂,其中首址256(256—383)的一半分给用户,其伙伴(首址384)挂到27空闲块链表中。 (5)11〈=16=24,因无24空闲块,25产生分裂,一半(首址32(32—47))分给用户,其伙伴(首址48)挂到24大小的空闲块链块表。 (6)19〈=32=25。因无25空闲块,26块分裂,一半(首址192(192—223))分给用户,其伙伴(首址224)挂到25空闲块链表中。 总之,6个用户占用块首址依次为0,64,128,256,32和192,这时可利用空间表的状态为: 3、回收 (1)(1)45〈=26=64,其首址为64,因64 MOD 26+1=26,所以其伙伴地址为64-64=0(不空)其伙伴占用,故仅将此结点挂到26空闲块链表中。 (2)(2)52<=26=64,其首址为128,因128 MOD 26+1=0,所以,伙伴地址=128+64=192(占用),故仅将此块挂到26空闲块链表中。 (3)(3)11〈=24=16,首址32 因32 MOD 24+1=0,伙伴地址32+24=48(空闲),故合并成25(块)。 因32 MOD 25+1=2,新伙伴地址为32-32=0(不空),故将25一块挂于 25的空闲块链表中。 总之,三块释放后空闲表状态如下: 第九章查找 一、一、内容提要 1、1、本章介绍的查找表是称为集合的数据结构。是元素间约束力最差的数据结构: 元素间的关系是元素仅共在同一个集合中。 2、查找表的操作:查找,检索,插入,删除,成员关系判断。 3、静态查找表:顺序表,有序表,静态树表,索引顺序表。 4、动态查找表:二叉排序树,平衡二叉树,B-树,B+树,键树。 5、哈希表。 二、二、学习重点 1、查找表是称为集合的数据结构。因元素间关系非常松散,其操作需借助其它数据结构 来实现。本章列举了三种方法(静态查找表,动态查找表,哈希表)实现查找表的运算。 2、顺序表因引设置了监视哨使查找效率大大提高。有序表的平均查找长度不超过树的深度,其判定树是唯一的。索引顺序查找综合了上述二者的优点,既能较快速的查找,又能适应动态变化的要求。 3、二叉排序树的形态取决于元素的输入顺序。按中序遍历可得到结点的有序序列,应熟 练掌握其建立、查找,插入和删除算法。 4、4、最佳二叉排序树是平均查找长度最短的二叉排序树,平衡二叉树是介于最佳和一 般间的折中,应熟练掌握手工绘制平衡二叉树。 5、5、键树中每个结点是关键字的一个字符,该树是有序树(同层兄弟间从左到右递增, 最 小是结束符号$)。 6、6、哈希表是查找表(集合)的又一表示方法,根据选定的哈希函数和处理冲突的方 法,将关键字映像到哈希表中。冲突是不可避免的。 7、7、哈希表中关键字的查找只能用哈希函数来计算,不能顺序、折半查找。元素删除 也只能作标记,不能物理的删除。 三、例题解析 1.设二叉排序树中元素均为整数,试编写算法从大到小输出各元素值。 【分析】中序遍历二叉排序树可得元素的有(升)序序列。 【算法】 PROC bstoutput (bst:bitreptr); {bst是二叉排序树根结点指针,本算法从大到小输出二叉排序树的各结点的值} IF bst<>NIL THEN [ bstoutput (bst↑.rchild); write (bst↑.data:5); bstoutput(bst↑.lchild); ]; ENDP;{bstoutput} 【讨论】课本中讨论了二叉树的三种递归遍历算法,另三种并非没用。本题就是先中序遍历右子树,再访问根结点,最后中序遍历左子树。本题另一种解法是在中序遍历二叉排序树,访问根结点时将结点值进栈保存,遍历结束后依次弹出栈中元素,直至栈空,所得结果亦符合要求,但多用了一个栈,不如这里所采用的算法简单。 2.编写在二叉排序树上插入结点s的算法。 【分析】二叉排序树上插入结点都是在叶子上插入。 【算法】 PROC insert (V AR bst: bitreptr;;s:bitreptr); {本算法在二叉排序树bst 上插入结点s} IF bst =NIL THEN bst:=s ELSE IF bst.data>s↑.data THEN insert (bst↑.lchild,s) ELSE insert (bst↑.rchild,s); ENDP; {insert} 【讨论】这是最简洁的递归算法。 3.编写在索引顺序表中查找数据k的算法。 【分析】索引顺序查找又称分块查找,设表中共有n个记录,每块中有s个记录,故共有b=┌(n/s)┐(上取整)块。 现设一索引表,其结构如下: TYPE idxtb1=RECORD key: keytype; low,high:integer; END; Index=ARRAY[1..b]OF idxtbl; 记录中三个域:key为索引所指块中最大关键字,low和high指该块中最低下标值和最高下标值。先折半查找索引表,再顺序在索引所指的某块内查找。 【算法】 FUNC indxblk( r:seqlisttp: idx:index; k:keytype):integer; {本算法在索引顺序表r中,查找其关键字值为待查元素值k的元素。Idx是索引表} low:=1;high:=b;{在索引表中折半查找其值>=k的最小元素} found:=false; WHIEL (low<=high)AND NOT found DO [ mid:=(low+high)DIV 2; CASE r[mid].key=k:low:=mid; found:=true; r[mid].key>k::high:=mid-1; r[mid].key ENDC;{若查找失败low值即为所求} IF low>b THEN low:=b; {取最后一块} l:=idx[low].low; {取待查块在r中的最低和最高下标} h:=idx(low).high; i:=l; WHILE (r[i].key<>k) AND (i<=h) DO i:=i+1; IF r[i].key=k THEN idxblk:=i ELSE idxblk:=o; ENDF;{indxblk} 4.已知一个含有100个记录的表,关键字是中国人名的拼音。请给出此表的一个哈希表设计方案。要求在等概率情况下查找成功的平均查找长度不超过3。 【分析】 (1)根据平均查找长度不超过3,确定装填因子α; snl≈1/2(1+(1/(1-α))){使用线性探测再散列解决冲突} 因snl<=3,所以α至少为0.8,取α=0.8. (2)根据α确定表长 由α=(表中添入的记录数)/(哈希表的长度) 所以哈希表的长度=100/α=125 取表长=150; (3)选取哈希函数 H(key)=key MOD 149 (4) key 的选取方法。 设大写字母在表中用1..26 表示,小写字母用27--52 表示。每个人的姓名取四个字母(两字姓名取首尾两个字母,三字姓名取各字拼音第一个字母,中间字取首尾两个拼音字母)。 将前两个拼音字母的序号并起来,后两个也并起来, 然后相加形成关键字。要求姓名的第一个拼音字母要大写,如姓名'王丽明'拼音为'Wang liming',取出四个拼音字母为'W,l,i,m',个字母序号依次为23 38 35 39,组成关键字为2338+3539=5877,该姓 名的哈希地址为5877 MOD 149=66。 (5)(5)用线性探测再散列处理冲突。 第十章第十章内部排序 一、内容提要 1、排序的定义,排序可以看作是线性表的一种操作 2、排序的分类,稳定排序与不稳定排序的定义。 3、插入排序(对分插入、二路插入、表插入、希尔插入排序)。 4、交换排序(冒泡排序、快速排序)。 5、选择排序(简单选择排序、树形选择排序、堆排序)。 6、归并排序、基数排序。 二、学习要点 1.1.各种排序所基于的基本思想。 2.2.在“最好”和“最差”情况下,排序性能的分析,是否是稳定排序的结论。 3.3.插入排序基于假定待排序文件第一个记录有序,然后从第二个记录起,依次插入到已排好序的有序子文件中,直到整个文件有序。从减少比较次数和移动次数进行了各种改进,产生了折半、二路、表插入、希尔等一系列插入排序。 4.4.交换排序基于相邻记录比较,若逆序则进行交换。冒泡排序和快速排序是交换排序的例子,快速排序是目前最快的内部排序法。应采用“三者取中”法防止其性能退化。 5.5.简单选择排序、树形选择排序、堆排序是选择排序的例子。堆排序较为重要,其最差性能比快速排序的最差性能好(Olog n) 6.6.归并排序、基数排序及时间复杂度O(n2)的排序为稳定排序,而希尔排序、快速排序、堆排序等时间性能好的排序方法,包括简单选择排序,是不稳定排序。 7.7.对每种排序方法的学习,应掌握其本质(排序所基于的思想),并能举一反三。 二、例题解析 1.1.设待排序文件有n ( n>0 )个记录,试编写算法,不经全部排序,将第j (0 【分析】将该记录作枢轴,进行一趟快速排序,则可将该记录放在其排序后应在的位置上。 【算法】 PROC quickpass(VAR r:listtype;j:integer); {本算法将第j个记录快速放到它排序后的位置上} IF j<>1 THEN r[j] ←→ r[1]; i:=1; k:=n; rp:=r[i]; x:=r[1].key; WHILE i [ WHILE (i IF i WHILE (i IF i ] r[i]:=rp; ENDP;{quickpass} 【讨论】本题的一种变形可叙述为:不经全部排序,求出排序后第j(0 置的元素。即,若将n个记录排序后,该元素是第j个记录。 设待排序文件的记录下标的下界、上界是s和t,根据一趟快速排序,求出 第一个元素(枢轴)所在位置i,若i=j则该位置即为所求,若i 中去找j,否则到(s··i-1)中去求,直到i=j为止。 PROC Quicksort_J(V AR r:Listype; j:integer;V AR rp:rcdtype); {求记录序列r[1..n]中排序后第j个的记录rp。} s:=1; t:=n; quickpass( r,s,t,k) WHILE k<>j DO IF k ELSE quickpass( r,s,k-1,k) rp:=r[j] ENDP; {Quicksort_J} PROC quickpass(V AR r:Listype;s,t: integer;V AR k:integer); i:=s; j:=t; rp:=r[i]; x:=r[i].key; WHILE i [ WHILE (i IF (i WHILE (i IF (i ] r[i]:=rp; k:=i ENDP; {end of quickpass} 2.已知(k1,k2,┄,kp)是堆,试编写算法将(k1,k2,┄,k[p],k[p+1])调整为堆。 算法复杂度为O(logn). 【分析】因为(k1..k p)是堆,加入k p+1相当于在向量中加入第p+1个元素,只要沿其双亲方向调整,直到满足堆的定义为止。 【算法】 PROC Ajustheap(VAR r:listtyp;p:integer); {已知(k1..k p)是堆,加入k p+1,本算法将(k1,k2,┄,k[p],k[p+1])调整为堆。} c:=p+1; f:=c DIV 2; {f是c 的双亲} C语言模拟试题 一、判断 1、关系运算符<= =与= =的优先级相同。(N ) 2、C语言的函数可以嵌套定义。(N ) 3、若有定义和语句:int a;char c;float f;scanf(“%d,%c,%f”,&a,&c,&f);若通过键盘输入:10,A,12.5, 则a=10,c=?A?,f=12.5.( Y ) 4、变量根据其作用域的范围可以分作局部变量和全局变量。( Y ) 5、#define和printf都不是C语句。( Y ) 6、Int I,*p=&I;是正确的C说明。( Y ) 7、结构体类型只有一种。( N ) 8、在Turbo C中,整形数据在内存中占2个字节。( N ) 9、一个include命令可以指定多个被包含的文件。( N ) 10、有如下说明:int a[10]={1,2,3,4,5,6,7,8,9,10},*p=a;则数值为9的表达式是*(p+8).( Y ) 二、选择 2、C语言中,char类型数据占(A) A、1个字节 B、2个字节 C、4个字节 D、8个字节 3、已知x=43,ch=?A?,y=o;则表达式(x>=y&&ch1;i--) for(j=1;j 江西理工大学考试试卷 1、C语言中的基本类型包括_____B_____ A.整型、实型、逻辑型B.整型、实型、字符型 C.整型、逻辑型、字符型 D. 整型、实型、逻辑型、字符型 2、C语言中,合法的用户标识符是(A ) A._a10 B.ab.txt C.return D.3ab 3、以下叙述中,不正确的是( A ) A.C语言程序中可以有若干个main()函数 B.C语言程序必须从main()函数开始执行 C.C语言程序中必须要有main()函数 D.C语言程序是由若干个函数组成 4、以下选项正确的定义语句是( C) A. double a; b; B.double a=b=7; C. double a=7,b=7; D. double ,a,b; 5、设“double x=1,y;”表达式y=x+3/2的值是_________ A. 1 B. 2 C. 2.0 D. 2.5 6、以下能正确定义二维数组的语名为_____D_______。 A.int a[][]; B.int a[][]4; C.int a[3][]; D.int a[3][4]; 7、C语言中,正确表示“1030”的条件表达式为______________。 A.(a>10&&a<20)&&(a>30) B.(a>10&&a<20)||(a>30) C.(a>10||a<20)||(a>30) D.(a>10&&a<20)||!(a<30) 8、设“int a=9;”,语句“a+=a-=a+a;”执行后,变量a的值是( C ) A.18 B.9 C.-18 D.-9 9、在以下一组运算符中,优先级最高的是:(C) A、<= B、== C、% D、&& 10、已知字母A的ASCII码为65,以下语句段的输出结果是____________。 Char c1=’A’,c2=’Y’; printf(“%d,%d\n”,c1,c2); A.输出格式非法,输出错误信息B.65,90 C.A,Y D.65,89 11、关于if后面一对圆括号中的表达式,叙述正确的是_______ A.只能用关系表达式 B 只能能逻辑表达式 C.只能用关系表达式或逻辑表达式 D 可以使用任意合法的表达式 12、C程序编译后最终产生(即计算机可执行)的文件的扩展名为( A ) A..exe B..c C..obj D..cpp C语言程序设计基础测试题 一、单选 [1] 下面叙述中错误的是____。 A. 复合语句中定义的函数只在该复合语句中有效 B. return( )语句中的括号中,可以是变量,常量或有确定值的表达式 C. 形式参数也是局部变量 D. 主函数中定义的变量在整个程序中都是有效的 [2]下列说法中正确的是____。 A.带参数的宏定义中的参数是没有类型的 B.宏展开将占用程序的运行时间 C.宏定义命令是C语言中的一种特殊语句 D.使用#include命令包含的头文件必须以“.h"为后缀 [3.] 若函数的形参为一维数组,则下列说法中正确的是____。 A.调用函数时的对应实参必为数组名 B.形参数组可以不指定大小 C.形参数组的元素个数必须等于实参数组的元素个数 D.形参数组的元素个数必须多于实参数组的元素个数 [4]. 系统的标准输出设备是____。 A.键盘 B.硬盘 C.内存 D.显示器 [5] 下面叙述中正确的是____。 A.全局变量在定义它的文件中的任何地方都是有效的 B.全局变量在程序的全部执行过程中一直占用内存单元 C. C语言的switch语句中case后可为常量或表达式或有确定值的变量及表达式 D. 说明函数时必须明确其参数类型和返回类型 [6]. C程序的基本结构单位是____。 A.文件 B.语句 C.函数 D.表达式 [7] 对于定义,char *aa[2]={"abcd","ABCD"},选项中说法正确的是____。 A.aa数组元素的值分别是"abcd"和"ABCD" B.aa是指针变量,它指向含有两个数组元素的字符型一维数组 C.aa数组的两个元素分别存放的是含有4个字符的一维字符数组的首地址 D.aa数组的两个元素中各自存放了字符'a'和'A'的地址 [8]. 任何一个C语言的可执行程序都是从____开始执行的。 A.程序中的第一个函数 B.main( )函数的入口处 选择题1.下列字符序列中,不可用作C语言标识符的是()。 A.abc123 B.C._123_ D._ok 2.请选出可用作C语言用户标识符的一组标识符()。 A.void B.a3_b3 C.For D.2a define _123 -abc DO WORD IF Case sizeof 3.不属于C语言关键字的是()。 A.int B.break C.while D.character 4.以下不能定义为用户标示符的是()。 A.scanf B.Void C._3com_ D.int 5.C语言程序的基本单位是()。 A.程序行B.语句C.函数D.字符 6.以下说法中正确的是()。 A.C语言程序总是从第一个定义的函数开始执行 B.在C语言程序中,要调用的函数必须在main( )函数中定义 C.C语言程序总是从main( )函数开始执行 D.C语言程序中的main( )函数必须放在程序的开始部分 7.以下选项中,合法的用户标识符是()。 A.long B._2abc C.3dmax D. 8.已知大写字母A的ASCII码值是65,小写字母a的ASCII码是97,则用八进制表示 的字符常量’\101’是()。 A.字符A B.字符a C.字符c D.非法的常量 9.以下选项中,正确的字符常量是()。 A.”F”B.’\\’’C.’W’D.’’ 10.下列变量定义中合法的是 A.short _a=; B.double b=1+; C.long do=0xfdaL; D.float 2_and=1-e-3; 11.为了避免嵌套的if-else语句的二义性,C语言规定else总是与()组成配对关系。 A.缩排位置相同的if B.在其之前未配对的if C.在其之前未配对的最近的if D.同一行上的if 12.下列运算符中优先级最高的是()。 A.< B.&& C.+ D.!= 13.判断char型变量s是否为小写字母的正确表达式是()。 A.’a’ <= s<=’z’B.(s>=’a’) & (s<=’z’) C.(s>=’a’) && (s<=’z’) D.(’a’<=s) and (’z’>=s) 学院***************** 目录 1 摘要 (3) 1.1设计题目 (3) 1.2设计内容 (3) 1.3开发工具 (3) 1.4应用平台 (4) 2 详细设计 (4) 2.1程序结构 (4) 2.2主要功能 (10) 2.3函数实现 (13) 2.4开发日志 (18) 3 程序调试及运行 (20) 3.1程序运行结果 (20) 3.2程序使用说明 (22) 3.3程序开发总结 (22) 4 附件(源程序) (22) 1 摘要 1.1 设计题目 折半法查找演示程序 1.2 设计内容 本程序是一个演示折半查找算法的演示程序。由用户输入查找的数据表列和查找的数据,系统在将数表排序后可以在屏幕上演示在排序后的表列中按折半查找法查找该数据的具体过程(通过每次查找的中间数据、下次查找表列等,具体效果见下图),支持多次演示、错误提醒,程序暂停演示功能。 1.3 开发工具 Visual C++ 6.0和Win32。 1.4 应用平台 Windows 2000/XP/Vista 32位 2 详细设计 2.1 程序结构 程序功能模块: 本程序主要由五大模块组成:程序说明模块、输入模块、排序模块、折半法查找及显示模块、进程选择模块。各模块的主要功能如下: 程序说明模块:给使用者营造一个较为友好的界面,同时提供程序开发人员的相关信息以及程序操作的相关说明信息。 此部分模块主函数源代码如下: int a[N]; /*存储要查找的数表,用户输入*/ int i,n,num,count; /*count为折半次数计数器,n为数表数据个数,num存储所查数据*/ int top,bottom,mid; char c; /*存储选择函数中的输入的字符y或n*/ int flag=1; /*折半法循环标志变量*/ int loc=-1; /*存储所查找数据位置*/ double k=0; p_s(76);puts("\n"); /*引用p_s函数,打出一行'*'*/(p_s函数位于print_star.cpp文件中,参见下文) printf("****欢****迎****使****用****折****半****查****找****法****演****示****器****\n"); puts("\n"); /*程序欢迎语*/ p_s(13); printf("制作者:***************** "); /*作者信息*/ p_s(4); printf("Email:************************ "); /*电子邮件*/ 精选考试类文档,如果您需要使用本文档,请点击下载! 祝同学们考得一个好成绩,心想事成,万事如意! 大学C语言考试试题及答案 姓名成绩 温馨提示:同学们,经过培训学习,你一定积累了很多知识,现在请认真、仔细地完成这张试题吧。加油! 一单项选择题 1. 在C语言中,以 D 作为字符串结束标志 A)’\n’ B)’ ’ C) ’0’ D)’\0’ 2.下列数据中属于“字符串常量”的是( A )。 A.“a” B.{ABC} C.‘abc\0’ D.‘a’ 若干个字符构成字符串 在C语言中,用单引号标识字符;用双引号标识字符串 选项B,C,分别用{}和’’标识字符串 选项D,标识字符。 3、以下说法中正确的是( C )。 A、C语言程序总是从第一个定义的函数开始执行 B、在C语言程序中,要调用的函数必须在main( )函数中定义 C、C语言程序总是从main( )函数开始执行 D、C语言程序中的main( )函数必须放在程序的开始部分 4.下列关于C语言的说法错误的是( B )。 A) C程序的工作过程是编辑、编译、连接、运行 B) C语言不区分大小写。 C) C程序的三种基本结构是顺序、选择、循环 D) C程序从main函数开始执行 5.下列正确的标识符是(C )。 A.-a1 B.a[i] C.a2_i D.int t 6.下列C语言用户标识符中合法的是( B )。 A)3ax B)x C)case D)-e2 E)union 7.下列四组选项中,正确的C语言标识符是( C )。 A) %x B) a+b C) a123 D) 123 8、下列四组字符串中都可以用作C语言程序中的标识符的是( A )。 A、print _3d db8 aBc B、I\am one_half start$it 3pai C、str_1 Cpp pow while D、Pxq My->book line# His.age 9.C语言中的简单数据类型包括(D )。 A、整型、实型、逻辑型 B、整型、实型、逻辑型、字符型 C、整型、字符型、逻辑型 D、整型、实型、字符型 10.在C语言程序中,表达式5%2的结果是 C 。 A)2.5 B)2 C)1 D)3 11.如果int a=3,b=4;则条件表达式"a C语言程序设计(B) (2010-2011-2) 实验报告 教学班级:学号:姓名: 课程教师:王华金实验辅导教师:王华金 P123--五、1、编写函数,找出5*5数组对角线上元素的最小值,并在主函数中调用它。要求元素的值通过键盘输入。 实验前的源程序: #include 谭浩强C语言知识点总 结 文件编码(GHTU-UITID-GGBKT-POIU-WUUI-8968) C语言最重要的知识点总体上必须清楚的: 1)程序结构是三种: 顺序结构、选择结构(分支结构)、循环结构。 2)读程序都要从main()入口, 然后从最上面顺序往下读(碰到循环做循环,碰到选择做选择),有且只有一个main函数。 3)计算机的数据在电脑中保存是以二进制的形式. 数据存放的位置就是他的地址. 4)bit是位是指为0 或者1。 byte 是指字节, 一个字节 = 八个位.概念常考到的: 1、编译预处理不是C语言的一部分,不占运行时间,不要加分号。C语言编译的程序称为源程序,它以ASCII数值存放在文本文件中。 2、define PI ; 这个写法是错误的,一定不能出现分号。 3、每个C语言程序中main函数是有且只有一个。 4、在函数中不可以再定义函数。 5、算法:可以没有输入,但是一定要有输出。 6、break可用于循环结构和switch语句。 7、逗号运算符的级别最低,赋值的级别倒数第二。 第一章 C语言的基础知识 第一节、对C语言的基础认识 1、C语言编写的程序称为源程序,又称为编译单位。 2、C语言书写格式是自由的,每行可以写多个语句,可以写多行。 3、一个C语言程序有且只有一个main函数,是程序运行的起点。 第二节、熟悉vc++ 1、VC是软件,用来运行写的C语言程序。 2、每个C语言程序写完后,都是先编译,后链接,最后运行。(.c---?.obj---?.exe)这个过程中注意.c和.obj文件时无法运行的,只有.exe文件才可以运行。(常考!) 第三节、标识符 1、标识符(必考内容): 合法的要求是由字母,数字,下划线组成。有其它元素就错了。 并且第一个必须为字母或则是下划线。第一个为数字就错了 2、标识符分为关键字、预定义标识符、用户标识符。 关键字:不可以作为用户标识符号。main define scanf printf 都不是关键字。迷惑你的地方If是可以做为用户标识符。因为If中的第一个字母大写了,所以不是关键字。 预定义标识符:背诵define scanf printf include。记住预定义标识符可以做为用户标识符。 用户标识符:基本上每年都考,详细请见书上习题。 第四节:进制的转换 十进制转换成二进制、八进制、十六进制。 二进制、八进制、十六进制转换成十进制。 第五节:整数与实数 1)C语言只有八、十、十六进制,没有二进制。但是运行时候,所有的进制都要转换成二进制来进行处理。(考过两次) 江西理工大学考试试卷 班级学号姓名 一、单项选择题(每题2分,共40分) 1、C语言中的基本类型包括__________ A.整型、实型、逻辑型B.整型、实型、字符型 C.整型、逻辑型、字符型 D. 整型、实型、逻辑型、字符型 2、C语言中,合法的用户标识符是() A._a10 B.ab.txt C.return D.3ab 3、以下叙述中,不正确的是( ) A.C语言程序中可以有若干个main()函数 B.C语言程序必须从main()函数开始执行 C.C语言程序中必须要有main()函数 D.C语言程序是由若干个函数组成 4、以下选项正确的定义语句是() A. double a; b; B.double a=b=7; C. double a=7,b=7; D. double ,a,b; 5、设“double x=1,y;”表达式y=x+3/2的值是_________ A. 1 B. 2 C. 2.0 D. 2.5 6、以下能正确定义二维数组的语名为____________。 A.int a[][]; B.int a[][]4; C.int a[3][]; D.int a[3][4]; 7、C语言中,正确表示“1030”的条件表达式为______________。 A.(a>10&&a<20)&&(a>30) B.(a>10&&a<20)||(a>30) C.(a>10||a<20)||(a>30) D.(a>10&&a<20)||!(a<30) 8、设“int a=9;”,语句“a+=a-=a+a;”执行后,变量a的值是( ) A.18 B.9 C.-18 D.-9 9、在以下一组运算符中,优先级最高的是:() A、<= B、== C、% D、&& 10、已知字母A的ASCII码为65,以下语句段的输出结果是____________。 1:2:3 #include } } } return 0; } 8 #include"stdio.h" int main() { int a,b[10],m=0,n=0,p; int i,j,k; scanf("%d",&a); for(i=1;i<=a;i++) { m=0; n=0; p=i; for(j=0;p!=0;j++) { b[j]=p%10; p=p/10; } for(k=0;k ================================================== 题号:1482 执行以下程序段后,输出结果和a的值是()。int a=10; printf("%d",a++); A、11 和10 B、11 和11 C、10 和11 D、10 和10 答案: C 题号:2100 已知字符'A'的ASCⅡ代码值是65,字符变量c1的值是'A',c2的值是'D'.执行语句printf("%d,%d",c1,c2-2);后,输出结果是 A、65,66 B、A,B C、65,68 D、A,68 答案: A 题号:5055 相同结构体类型的变量之间,可以()。 A、比较大小 B、地址相同 C、赋值 D、相加 答案: C 题号:3217 int a[10];合法的数组元素的最小下标值为()。 A、1 B、0 C、10 D、9 答案: B 能正确表示逻辑关系:" a≥10或a≤0 "的C语言表达式是 A、a>=0 | a<=10 B、a>=10 or a<=0 C、a>=10 && a<=0 D、a>=10 || a<=0 答案: D 题号:157 main() {int x=1,a=0,b=0; switch (x) { case 0: b++; case 1: a++; case 2: a++;b++;} printf("a=%d,b=%d",a,b); }该程序的输出结果是( ) A、2,2 B、2,1 C、1,1 D、1,0 答案: B 题号:4784 设变量a是整型,f是实型,i是双精度型,则表达式10+'a'+i*f值的 数据类型为()。 A、不确定 B、double C、int D、float 答案: B 题号:1647 以下程序中,while循环的循环次数是______ main() { int i=0; 江西理工大学 广东顺德工业设计研究院(广东顺德创新设计研究院)2019年硕士研究生联合培养项目招生简章 为创新专业学位研究生培养模式,提高研究生实践、创新和职业发展能力,江西理工大学与广东顺德工业设计研究院(广东顺德创新设计研究院)开展联合培养研究生项目,共同招收、培养研究生。 一、项目特色 以江西理工大学和广东顺德工业设计研究院(广东顺德创新设计研究院)为平台,以顺德智能制造产业为依托,实行“理论学习+企业实践”的双课堂教学形式,结合传统课堂教学方法,以企业项目导入的方式,参与企业实际项目的开发与研究,从理论学习、实践技能和职业能力发展需求等方面进行多角度、多层次的教学和实践。 二、培养目标 培养符合智能家电、智能装备、生命科学仪器产业发展需要,掌握扎实的现代电子信息技术专业和软件开发基础知识,具备创新思维和工程实践能力,具有良好职业素养以及多领域融合的高层次应用型、复合型人才,为成为智能产业工程师打下坚实基础。 三、招生对象和报名条件 符合教育部相关文件要求的各类考生,具体要求详见《江西理工大学2019年硕士研究生招生简章》。 四、报名、考试与录取 报名方式为推荐免试或公开报考。推荐免试按《江西理工大学2019年接收推免攻读硕士学位研究生简章》执行。公开报考考生应参加全国招收攻读硕士学位研究生的报名和统一入学考试,具体要求见《江西理工大学硕士研究生招生简章》。 拟安排20-30名招生计划,按照“单列计划、联合培养”的原则,由江西理 工大学—广东顺德工业设计研究院(广东顺德创新设计研究院)联合培养项目单独组织复试、录取工作。 五、学习年限及培养方式 联合培养项目以江西理工大学硕士研究生培养方案为基础,以“课程与职业需求对接、教学与生产实际结合”的原则,采取项目教学化、教学项目化的项目导入教学方式进行专业学位研究生培养。 基本学制3年,以1+2年的分段学习方式完成。第一学年在江西理工大学完成基础课程学习,第二、三学年在广东顺德工业设计研究院(广东顺德创新设计研究院)学习,依托顺德家电企业,以项目导入方式参与企业项目开发和研究,第三学年完成学位论文并参加答辩。 六、毕业和学位授予 在规定年限内,完成培养方案的规定课程和必修环节,获得相应学分,成绩合格,完成学位论文并通过答辩,达到江西理工大硕士学位基本要求,经江西理工大学校学位评定委员会审核批准,授予工程硕士专业学位,颁发学位证书和毕业证书。 七、广东顺德工业设计研究院(广东顺德创新设计研究院)简介 广东顺德工业设计研究院(广东顺德创新设计研究院)(以下简称“研究院”)于2014年正式成立,是顺德区直属事业单位,以创新创业孵化、企业科技服务和研究生联合培养为核心业务,以精密仪器研发、信息技术、机械自动化、工业设计等为主要研究领域,以“建设技术创新生态、服务顺德产业升级、培养高级复合人才”为宗旨,建设成为“政产学研”一体化的协同创新平台。 研究院开展先进医疗设备、智能制造装备、新能源等高科技产品研发与工程化项目10项,产出4个新产品样机(数字PCR仪器、常温下离体肝脏机械灌注设备、废液安全收集器、震动泡沫轴),申请创新医疗器械特别审批并通过了初审。作为新型研发机构,研究院重点围绕科技创新、区域产业发展的需求,积极推进服务于区域产业发展的加强生物医学技术、智能制造协同创新平台建设。 研究院聚焦生物医学领域,搭建高起点、国际化的科研协同创新平台。一是与西班牙的国际器官捐献与移植研究院、广州军区广州总医院合作共建“器官研究与发展国际基地”(国际合作协同创新中心),引进国际顶尖资源,开展具有国 常量和变量 1.常量: 程序执行过程中,值不变的量。 3 ,'a' 变量:值可以改变的量。 一个变量有一个名字,在内存中有一定的存储单元,存放变量的值。 2.常量类型: a.整型:12,0,-3 b.实型:4.6,-1.2 c.字符型: 'a','d' d.符号常量: #define PRICE 30 (PRICE不能再被赋值且要大写) 3.变量: 先定义,后使用。一个变量只能被指定为一确定类型。 4.标识符:标识变量名,符号常量名,函数名,数组名,类型名,文件名的有效字符数列。 a.由字母、数字、下划线三种字符组成,第一个字符必须为字母或下划线。 b.大写字母、小写字母被认为是两个不同的字符。 c.长度一般小于8个。 数据类型 一.整型: 1.整型常量 a.十进制:12,-3,0 b.八进制:以0开头。 c.十六进制:以0x开头。 2.整型变量 a. int -32768——32767 b. short int -32768——32767 c. long int d. unsigned int 0——65535 e. unsigned short 0——65535 f. unsigned long int、short int、long int 第一位为符号位 0000001 (0为正,1为负) unsigned 第一位不是符号位 0000001 所以int型和unsigned型的000001不是同一个值。 二.实型: 1.实型常量: a.十进制数:数字和小数点组成。0.12,.12,12.0,0.0 b.指数:e之前必须有数字,e后面必须为整数。12e3 2.实型变量: a.单精度:float 7位有效数字 111111.1可,111111.11不可。 b.双精度:double 15—16位有效数字。 三.字符型: 1.字符常量: a. 'a' , 'x' , '*' ,'$' 。 b. 转义字符:‘\n'换。 '\t'从第九列开始。'\r'回车。 '\b'退一格。 2.字符变量: char char='a' 一个字符变量在内存占一个字节。 。将一个字符常量放到一个字符变量中,并不是把该字符本身放到内存单元中去,而是将该字符的ASC码 放到存储单元中,所以字符型数据和整型数据之间可以通用。一个字符型数据既可以以字符形式输出, 又可以以整数形式输出。 四.字符串常量: "how are you", "a","&12" 。不能把一个字符串赋给一个字符变量。 char c='a'对,char c="how" 错。 。'a' :在内存中存a。 “a”:在内存中存a\0。 ‘\0’是C语言中判断字符串是否结束的标志。 变量赋初值 a. int a=3; float f=7.2; char c='a'; b. int a,b,c=5; 相当于 int a,b,c; c=5; c. int a=3;b=3;c=3; 不可写: int a=b=c=3; 《C语言程序设计》期中考试试卷 课程编号:03402513试卷类型:A卷考试形式:笔试考试日期: 注意事项:1.请将试卷最后一页的答题纸撕下,将答案填写在其中;2.交卷时请确认答题纸是否按要求写好姓名等信息并与试题一起上交;3.不准携带任何书籍、资料、纸张等。4.草稿纸用试卷的背面。 一、单项选择题(1空1分,共20分) 1、C语言程序的基本结构是(【1】) 。 【1】 A) 函数 B) 语句 C) 字符 D) 程序行 2、一个C程序的执行是(【2】) 。 【2】A) 从本程序的主函数开始,到本程序的主函数结束 B)从本程序的第一个函数开始,到本程序的最后一个函数结束 C) 从本程序的主函数开始,到本程序的最后一个函数结束 D)从本程序的第一个函数开始,到本程序的主函数结束 3、下列四个叙述中,错误的是(【3】) 。 【3】 A) 一个C源程序必须有且只能有一个主函数 B) 一个C源程序可以含一个或多个子函数 C) 在C源程序中注释说明必须位于语句之后 D) C源程序的基本结构是函数 4、下面不属于C语言保留字的是(【4】) 。 【4】 A) short B) ELSE C) extern D) for 5、下列四个叙述中,正确的是(【5】) 。 【5】 A) 库函数也是C语言本身的组成部分 B) C语言中的输入输出操作是由相应语句完成的 C) 库函数是C编译系统提供的功能函数 D) 标题文件(头文件)可以在程序的函数内部调用 6、下列四组数据类型中,C语言允许的一组是(【6】)。 【6】 A) 整型、实型、逻辑型 B) 整型、实型、字符型 C) 整型、双精度型、布尔型 D) 整型、实型、复型 7、在C语言中不同数据类型的的长度是(【7】)。 【7】 A) 固定的 B) 由用户自己定义的 C) 任意的 D) 与机器字长有关 C语言程序设计 附件1:实验报告模板 C语言程序设计 实验报告 实验一简单的C程序 教学班级:冶金136 学号:01 姓名:张博 课程教师:胡春安实验教师:胡春安 完成时间:2015-2016学年第1学期 实验一简单的C程序 实验时间:2机时 一、实验目的 1. 熟悉C程序编辑环境,掌握主要菜单项的操作和作用。 2. 熟悉编写一个C程序的上机过程(编辑、编译、链接和运行)。 二、实验意义 通过上机实验,加深对第一章所学基本知识:C语言的基本结构和简单C 程序的理解。通过调试简单的C程序,让学生对C程序的编辑、编译、链接和运行有一个直观的体验和熟悉,激发学习的好奇心和兴趣,为后面的全面学习奠定非常必要的基础。 三、实验内容 1.验证实验 (1)掌握程序的编辑、编译、连接、运行、调试过程,按以下步骤进行实验。 ?输入源程序 #include 大学c语言必背基础知识_c语言基础知识大全 对于刚学计算机编程的同学来说,没一个编程知识都觉得很重要,其实不是的。下面小编为大家整理了相关大学c语言必背基础知识,希望大家喜欢。 大学c语言必背基础知识举例说明: printf(“-”,123 ); 第二部分有三位,大于指定的两位,原样输出123 printf(“]”,123 ); 第二部分有三位,小于指定的五位,左边补两个空格123 printf(“f”,1.25 ); 小数要求补足6位的,没有六位的补0,。结果为1.250000 printf(“%5.3f”,125 ); 小数三位,整个五位,结果为1.250(小数点算一位) printf(“%3.1f”,1.25 );小数一位,整个三位,结果为1.3(要进行四舍五入) 第三节数据输入1、scanf(“a=%d,b=%d”,">2、scanf(“%d,%d”,x,y);这种写法绝对错误,scanf的第二个部分一定要是地址!scanf(“%d,%d”,注意写成这样才可以! 3、特别注意指针在scanf的考察例如:int x=2;int *p=scanf(“%d”,x); 错误scanf(“%d”,p);正确scanf(“%d”,错误scanf(“%d”,*p)错误 4、指定输入的长度(考试重点)终端输入:1234567scanf(“-M%d”,x为12,y为3456,z为7终端输入:1 234567 由于1和2中间有空格,所以只有1位给xscanf(“-M%d”,x 为1,y为2345,z为67 5、字符和整型是近亲:int x=97;printf(“%d”,x); 结果为97printf(“%c”,x); 结果为a 6、输入时候字符和整数的区别(考试超级重点) scanf(“%d”,这个时候输入1,特别注意表示的是整数1 scanf(“%c”,这个时候输入1,特别注意表示的是字符‘1’ASCII为整数48。 补充说明: 1)scanf函数的格式考察: 注意该函数的第二个部分是scanf(“%d%d%*d%d”,跳过输入的第三个数据。 2)putchar ,getchar 函数的考查: 第六次CH1005 #include { int n; char a[500],b[500]={'\0'},*p1,*p2; gets(a); scanf("%d",&n); p1=a;p2=b; for(p1=p1+n;*p1!='\0';p1++,p2++) *p2=*p1; puts(b); return 0; } #include 一、单项选择题(每小题2分,共50分) 1、一个C程序的执行是从___A__。 A、本程序的main函数开始,到main函数结束 B、本程序的main函数开始,到本程序文件的最后一个函数结束 C、本程序文件的第一个函数开始,到本程序文件的最后一个函数结束 D、本程序文件的第一个函数开始,到本程序main函数结束 2、C语言程序的基本单位是___C___。 A、程序行 B、语句 C、函数 D、字符 3、请选出可用作C语言用户标识符的一组标识符___B___。 A、void B、a3_b3 C、For D、2a define_123-abcDO WORDIFasesizeof 4、假定x和y为double型,则表达式(x=2,y=x+5/2)的值是__C__。 A、、4 C、、 5、下列可以正确表示字符型常量的是___D__。 A、297 B、"a" C、"\n" D、'\t' 6、在C语言中,要求运算数必须是整型的运算符是__D__。 A、/ B、++ C、*= D、% 7、C语言中,复合语句的构成是将一系列语句置于__C__。 A、begin与end之间 B、方框号“[]”之间 C、花括号“{}”之间 D、圆括号“()”之间 8、有如下程序段,对应正确的数据输入是___A___。 floatx,y; scanf(”%f%f”,&x,&y); printf(”a=%f,b=%f”,x,y); A、<回车> B、,<回车> <回车> C、A=,B=<回车> D、回车> 9、以下程序段的输出结果是___D__。 inta=5678; printf(”%2d\n”,a); A、提示出错、无结果 B、56 C、78 D、5678 10、已知:charch='A';则下列表达式的值是__B__。 ch=(ch>='A'&&ch<='Z')?(ch+32):ch; A、A B、a C、Z D、z C语言程序的结构认识 用一个简单的c 程序例子,介绍c 语言的基本构成、格式、以及良好的书写风格,使小伙伴对 c 语言有个 初步认识。 例1:计算两个整数之和的c 程序: #include main() { int a,b,sum; /* 定义变量a,b ,sum 为整型变量*/ a=20; /* 把整数20 赋值给整型变量a*/ b=15; /* 把整数15 赋值给整型变量b*/ sum=a+b; /* 把两个数之和赋值给整型变量sum*/ printf( “ a=%d,b=%d,sum=%d\n” ,a,b,sum); /* 把计算结果输出到显示屏上*/ } 重点说明: 1、任何一个c 语言程序都必须包括以下格式: main() { } 这是c 语言的基本结构,任何一个程序都必须包含这个结构。括号内可以不写任何内容,那么该程序将不执行任何结果。 2、main() - 在c 语言中称之为“主函数” ,一个c 程序有且仅有一个main 函数,任何一个c 程序总是从 main 函数开始执行,main 函数后面的一对圆括号不能省略。 3、被大括号{ }括起来的内容称为main 函数的函数体,这部分内容就是计算机要执行的内容。 4、在{ }里面每一句话后面都有一个分号(; ),在c 语言中,我们把以一个分号结尾的一句话叫做一个 c 语 言的语句,分号是语句结束的标志。 5、printf( “ a=%d,b=%d,sum=%d\n” ,a,b,sum); 通过执行这条c 语言系统提供给我们直接使用的屏幕输出 函数,用户即可看到运行结果,本程序运行后,将在显示器上显示如下结果: a=20,b=15,sum=35 6、#include 注意:(1)以#号开头 (2)不以分号结尾这一行没有分号,所以不是语句,在c 语言中称之为命令行,或者叫做“预编译处理命令” 。 7、程序中以/* 开头并且以*/ 结尾的部分表示程序的注释部分,注释可以添加在程序的任何位置,为了提高程序的可读性而添加,但计算机在执行主函数内容时完全忽略注释部分,换而言之就是计算机当做注释部分不存在于主函数中。 C程序的生成过程 C程序是先由源文件经编译生成目标文件,然后经过连接生成可执行文件。 源程序的扩展名为.c ,目标程序的扩展名为.obj , 可执行程序的扩展名为.exe 。大学C语言考试试题
江西理工C语言程序设计(B)试卷题型参考
C语言基础知识_测试题
江苏大学大一c语言期末复习题汇总
西北工业大学C语言大作业实验报告
大学C语言考试试题及答案
C语言实验报告
谭浩强C语言知识点总结
江西理工大学C语言程序设计(B)试卷_杨崇联(A1)
西工大C语言上机考试题库
大学c语言考试题库含答案
西南大学与第三军医大学西南医院高层次拔尖创新人才培养
C语言基础知识
c语言期中考试试题及答案
C语言实验指导及报告模板
大学c语言必背基础知识_c语言基础知识大全
西工大c语言实验100题06
大一c语言考试试题
C语言基础知识(详细版)