531 final Flashcards
Output of the following program?
#incude <studio.h>
#include <stdib.h>
struct name {
int a;
};
int main(){
struct name *ptr;
int i,n=5;
ptr(struct name*)malloc(n*sizeof(struct name));
for(i=0;i<n; ++i{
(ptr+i)->a=n-i;
}
printf("%d\n", (ptr+3)->a);
free(ptr);
return 0;
}</stdib.h></studio.h>
2
using ascii chart what’s the output?
#incude <studio.h>
int main(){
char ch[6] = "CS531";
printf("%x", ch[2]);
return 0;
}</studio.h>
35 (%x is hexadecimal)
incude <studio.h></studio.h>
#include <stdib.h>
struct st{
int a[5];
char ch[10];
};
int main(void){
struct st obj;
struct st *stobj = &obj;
obj.a[3] = 7;
stobj->a[3] = 5;
strcpy(obj.ch, 'Midterm");
stobj->ch[1] = 32;
printf("\nobj.a[3]==%d obj.ch==%s \n", obj.a[3],obj.ch);
return 0;
}</stdib.h>
obj.a[3]== 5 obj.ch == M dterm
(32 is spacebar cuz dec in ascii)
output using ascii chart?
#incude <studio.h>
#include <stdib.h>
int main(int argc, char *argv[]){
if(argc ==1)
{
printf("Program name: %s\n", argv[0]);
}
else{
printf("%x\n"argv[1][2]);
}
return 0;
}</stdib.h></studio.h>
$ gcc MT c-o MT
$./MT CS531
35 (MT is argc and CS531 is argv, therefore you get [1][2] of argv which is 5 and then turn it into hexadecimal)
find output:
#incude <studio.h>
int main(){
char array[10] = "CS 531";
char *a_ptr = array;
int x=4;
printf("%s",a_ptr+x);
return 0;
}</studio.h>
31(a_ptr+x means it starts printing at 31 since x = 4)
time complexity for traversing a singly linked list?
O(N)
find output:
#incude <studio.h>
int main(){
int x[3][4] =
{
{110,161,302,453},
{11,16,30,45},
{1100,1600,3000,4500}
};
int y,z;
for{y=2;y>0;y--){
for(z=0;z<4;z+=2){
printf("$d\n",x[y][z]);
}
}
return 0;
}</studio.h>
1100,
3000,
11,
30
include <studio.h></studio.h>
int main(void){
int n=28,
lcv,
flag;
for(lcv=2, flag=1; lcv<=(n/2);lcv++){
if((n%lcv)==0){
if(flag)
printf(“%d \n”, n);
flag = 0;
printf(“%d\n”,lcv);
}
}
}
28
2
4
7
14
incude <studio.h></studio.h>
int main(){
int s=0,x,y,z=3;
for(x=0;x<z;x++)
for(y=x;y<z; y++)
s+= x*y;
printf(“%d\n”,s);
return 0;
}
7
get output, assume push pop and isEmpty as Stack functions (first in last out)
int main(){
int num1,quotient,rem;
num1 = 41;
quotient = num1;
while(qutient!=0){
rem = quotient%3;
quotient = quotient/3;
push(rem);
}
while(!isEmpty()){
printf(“%d”,pop());
}
return 0;
}
1112
using a stack data structure, the pop operationmay be categorized as having what computational time value?
O(1)
recursion base case
prove the statement true for some specific value or
values of n (usually 0 or 1).
induction step
assume the statement to be true for all positive
integers less than n, then use that fact to prove it true for n
BST depth
number of edges from the root to the node
BST height
number of edges from the node to its deepest leaf.
full binary tree
each node has either 0 or 2 children
complete bst
a binary tree which is completely filled with the possible exception of the bottom level which is filled left to right
preorder traversal
visit parent first then left and right children ( in that order)
inorder traversal
visit left child then parent and then the right child
postorder traversal
visit left child, then right child, and then parent
logarithms
each level has max 2^n amount of nodes. n being the height level from root.
BST vs Binary tree
Binary tree isn’t ordered. BST is.
each node contains one key
the keys in the left are less than the parent. the keys in the right are greater than the parent. no duplicates
deletion in BST
leaf nodes are trivial.
if the node being deleted only has one child then the node is replaced by the only child.
if the nose being deleted has two children, replace the deleted node with its inorder successor or inorder predecessor
pass by value vs pass by reference (int vs int *)
pass by value indicates a copy of the data that is passed to the function. any changes to the parameter have no affect on data in the calling function.
Pass by reference involves use of a reference parameter. it referes to the original data, therefore any changes made to the original data will be passed into the original variable.
01000011 convert into hexadecimal
split into 4 bit parts (0100) (0011) and then convert to decimals (12^2 = 4), (12^1 +1*2^0 = 3) therefore you get 0x43 (0x just says it’s hexadecimal). using ascii chart it becomes C
01000011 convert into decimal
(12^0 +12^1+1*2^6 = 67) = C
HEAP
Variables allocated on the heap, or dynamic variables, have their memory allocated at run time . This memory
remains allocated until explicitly freed by the program and, as a result, may be accessed outside of the block in which it was
allocated.
structure vs union
Structures in C is a user-defined data type available in C that allows to combining of data items of different kinds. Structures are used to represent a record.
Union in C is a special data type available in C that allows storing different data types in the same memory location. You can define a union with many members, but only one member can contain a value at any given time. Unions provide an efficient way of using the same memory location for multiple purposes.
Big and Little Endian
Big-Endian: the most significant byte is stored at the lowest
memory address.
Little-Endian: the least significant byte is
stored at the lowest memory address.
Bubble sort
sorting algorithm that iteratively
steps through an array while comparing
adjacent elements and swapping them if they
are in the wrong order. The iteration loops
until the array is sorted O(n^2)
strcmp
function compares two
strings s1 and s2. It returns an
integer less than, equal to, or greater
than zero if s1 is found, respectively,
to be less than, to match, or be
greater than s2.
fgets
reads a character string from the specified stream (use stdin for keyboard input) and stores it into the
string pointed to by str. It stops when either (n-1) characters are read, the newline character is read, or the end-of-file is reached, whichever
comes first. If any characters are read and there is no error, a null byte (ascii 0, or ‘\0’) is appended to end the string.
scanf vs fgets
Recall from lecture that while reading from the keyboard using scanf(), the ‘\n’ is
not read in from the input buffer
strncmp
function is similar,
except it compares only the first (at
most) n bytes of s1 and s2
strchr
function returns a pointer to the first occurrence of the character c in the string s.
arrays and pointers
&a[1] is equivalent to (a+1) AND, a[1] is equivalent to *(a+1).
&a[2] is equivalent to (a+2) AND, a[2] is equivalent to *(a+2).
&a[3] is equivalent to (a+3) AND, a[3] is equivalent to *(a+3)
Bit Operations:
c = FLAG1 & FLAG2; FLAG1 = 00111100
printf(“Line 1 - Value of c is %d\n”, c ); FLAG2 = 00001101
00001100 = 12
c = FLAG1 | FLAG2;
printf(“Line 2 - Value of c is %d\n”, c );
c = FLAG1 ^ FLAG2;
printf(“Line 3 - Value of c is %d\n”, c );
c = ~FLAG1;
printf(“Line 4 - Value of c is %d\n”, c );
c = FLAG1 «_space;2;
printf(“Line 5 - Value of c is %d\n”, c );
c = FLAG1»_space; 2;
printf(“Line 6 - Value of c is %d\n”, c );
The & (bitwise AND) in C takes two numbers as operands and does AND on every bit of two numbers. The result of AND is 1 only if both bits are 1.
The | (bitwise OR) in C takes two numbers as operands and does OR on every bit of two numbers. The result of OR is 1 if any of the two bits is 1.
The ^ (bitwise XOR) in C takes two numbers as operands and does XOR on every bit of two numbers. The result of XOR is 1 if the two bits are different.
The «_space;(left shift) in C takes two numbers, the left shifts the bits of the first operand, and the second operand decides the number of places to shift.
The»_space; (right shift) in C takes two numbers, right shifts the bits of the first operand, and the second operand decides the number of places to shift.
The ~ (bitwise NOT) in C takes one number and inverts all bits of it.
means either one can have one
&Mask
removes removes the bits that are 0 in mask
AVL tree
self balancing binary search tree, because it’s self balancing all operations are O(logn) (insertion,removal, lookup)
avl balance factor
difference between left and right subtrees, must be (-1,0,1) else it has to balance (<-1 means left rotation, >1 means right rotation)
rotations
look at avl tree rotations powerpoint
